leetcode
leetcode 501 ~ 550
任务调度器

任务调度器

难度:

标签:

题目描述

代码结果

运行时间: 45 ms, 内存: 17.7 MB


/*
 * 题目思路:
 * 利用 Java Stream API 简化代码逻辑。我们依然需要统计每种任务的频率,
 * 然后计算最短时间。与传统 Java 方法相比,Stream 提供了更简洁的代码风格。
 */
 
import java.util.*;
import java.util.stream.Collectors;
 
public class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Long> freqMap = Arrays.stream(tasks)
                .boxed()
                .collect(Collectors.groupingBy(c -> c, Collectors.counting()));
        List<Long> frequencies = new ArrayList<>(freqMap.values());
        Collections.sort(frequencies, Collections.reverseOrder());
        long maxCount = frequencies.get(0);
        long idleSlots = (maxCount - 1) * n;
        for (long freq : frequencies) {
            idleSlots -= Math.min(maxCount - 1, freq);
        }
        return (int) (idleSlots > 0 ? idleSlots + tasks.length : tasks.length);
    }
}

解释

方法:

该题解的思路是统计任务的频率,找到频率最高的任务。根据最高频率和冷却时间,计算完成所有任务所需的最短时间间隔。具体来说: 1. 如果冷却时间 n 为0,直接返回任务的总数,因为任务可以连续执行。 2. 统计每个任务的频率,找到最高频率 max_freq。 3. 计算最高频率的任务数量 max_count。 4. 计算最短时间间隔,取以下两者的较大值: - 任务总数 len(tasks)。 - (max_freq - 1) * (n + 1) + max_count,其中 (max_freq - 1) * (n + 1) 表示在最高频率的任务之间插入冷却时间后所需的时间单位,max_count 表示最高频率的任务本身所需的时间单位。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
如何计算最高频率任务的数量max_count,能否详细说明其在算法中的实际应用和意义?
在算法中,最高频率任务的数量`max_count`是指有多少种任务的出现频率等于所有任务中出现频率最高的值。这个计算通过统计在任务频率字典`task_freq`中频率值等于`max_freq`的任务种类来实现。具体的计算方法是通过一个生成器表达式遍历`task_freq.values()`,对于每一个频率值`f`,如果`f`等于`max_freq`,则计数器加一。这个值的计算对于理解任务调度的时间间隔至关重要,因为在插入冷却时间的间隔中,最高频率的任务会决定必须等待的最少时间段。例如,如果最高频率的任务有多种,那么在最后一个周期中,这些任务将不需要额外的冷却时间即可依次执行,从而影响总的任务完成时间。
🦆
如果任务的种类数量非常多,但每种任务的出现频率都很低,这种情况下算法的效率如何?会不会存在计算上的不必要复杂性?
在任务种类非常多但每种任务的出现频率都很低的情况下,算法仍然有效并且效率较高。通过使用`Counter`来统计每种任务的频率,算法的时间复杂度主要是O(N),其中N是任务列表的长度。尽管任务种类多,但由于每种任务的频率低,计算最高频率`max_freq`和最高频率任务的数量`max_count`通常也是高效的。这种情况下,最终计算的时间间隔可能接近于任务的总数,因为高频任务较少,导致冷却时间的影响减小。因此,这种情况下的计算并不会引入不必要的复杂性。
🦆
算法中提到使用Counter来统计任务频率,这种数据结构在处理大规模数据时的性能如何?
使用`Counter`来统计元素频率是一种非常高效的方法,特别是在处理大规模数据时。`Counter`是`collections`模块中提供的一个字典子类,专门为快速计数场景设计。它在内部实现了散列表(哈希表),因此统计每个元素的出现次数的时间复杂度是O(1),整体上对于列表的遍历是O(N),其中N是列表的长度。即使面对大量数据,`Counter`能够快速准确地计算出各个元素的频率,因此在性能上是非常可靠的。

相关问题

K 距离间隔重排字符串

K 距离间隔重排字符串

重构字符串

给定一个字符串 s ,检查是否能重新排布其中的字母,使得两相邻的字符不同。

返回 s 的任意可能的重新排列。若不可行,返回空字符串 "" 。

 

示例 1:

输入: s = "aab"
输出: "aba"

示例 2:

输入: s = "aaab"
输出: ""

 

提示:

  • 1 <= s.length <= 500
  • s 只包含小写字母