Task Sheduler、有序矩阵中第K小的元素和多数元素

Task Scheduler

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的 26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。

然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

示例

输入: tasks = ["A","A","A","B","B","B"], n = 2
输出: 8
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.

方法一 贪心选择法

思路

每一轮选择尽可能多的不超过 n + 1 个任务执行，直到所有的任务被执行完。

详解

1. 对任务按照剩余的次数进行降序排序，从剩余次数最多的任务开始依次来执行

2. 每次判断任务是否可以执行，如果可以把对剩余的任务数量 -1

3. 一轮跑完之后，要重新对任务进行排列，保证任务的排序是降序

const leastInterval = function (tasks, n) {
  const counts = Array(26).fill(0);
  tasks.forEach(v => {
    const index = v.charCodeAt() - 65; // 'A'.charCodeAt() 为 65
    counts[index]++;
  });
  counts.sort((a, b) => (b - a)); // 直接从大到小排
  let res = 0;
  while (counts[0] > 0) {
    let i = 0;
    while (i < n + 1) { // 保证这一轮任务距离上次执行至少冷却 n 个单位的时间
      if (counts[0] === 0) { // 当最大当任务数为 0，跳出循环
        break;
      }
      if (i < 26 && counts[i] > 0) { // 判断任务是否可以执行
        counts[i]--;
      }
      res++;
      i++;
    }
    counts.sort((a, b) => (b - a)); // 每次任务执行完，保证最多的任务排在最前面
  }
  return res;
};

复杂度分析

• 时间复杂度：$O(time)$​

  通过 $res++$ 我们发现，最终的时间为多少，时间复杂度就是多少，这种解法的缺点在于，得出相当于是把每个任务执行了一遍

• 空间复杂度：$O(1)$​

  与 n 无关，申请数组的长度最大为26，复杂度为 $O(1)$​

方法二 桶思想

思路

换一种形象的比喻，把间隔时间必做桶。

每个桶固定大小为 n + 1，最后一个除外，把相同的任务分在不同的桶中，那么桶的数量就由数量最多的任务的数量来决定

可以得到结果为 $(n + 1) * (count - 1) + 最后一个桶的任务数$，至于说最后一个桶对任务数是多少，通过找规律发现，即为有多少个最多任务数

比如 ["A","A","A","B","B","B"]，即为 2，因为 A 和 B 的数量最多且一样

还有一种情况，当没有出现等待时，比如 ["A", "A", "B", "C", "D"]，间隔 n = 2 的时候，此时最小时间就是任务的长度明显是 4

但是发现上面的公式得出的值为1，不对了，此时我们只需要取两个数的最大值就可以了

详解

1、将任务按类型分组，把字母转为数字做数组的索引存在数组里

2、对数组进行排序，找出上面公式的 count 和 最后一个桶的任务数

3、最后套公式就可以得出答案了

const leastInterval = function (tasks, n) {
  const counts = Array(26).fill(0);
  tasks.forEach(v => {
    const index = v.charCodeAt() - 65; // 'A'.charCodeAt() 为 65
    counts[index]++;
  });
  counts.sort((a, b) => (b - a)); // 直接从大到小排
  const max = counts[0];
  const maxCount = counts.filter(a => a === max).length; // 多少个最多任务数
  const res = (n + 1) * (max - 1) + maxCount;
  return res > tasks.length ? res : tasks.length;
};

复杂度分析：

• 时间复杂度：$O(n)$​

  ​$n$ 为任务的总数

• 空间复杂度：$O(1)$​

  与 n 无关，申请数组的长度最大为26，复杂度为 $O(1)$​

有序矩阵中第K小的元素

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。 请注意，它是排序后的第k小元素，而不是第k个元素。

示例

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
​
返回 13。

说明 你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

方法一

思路

将二维数组展开为一维升序数组，取第 k-1 位。

详解

1. 将数组使用reduce展开为一维数组。

2. 使用数组的sort方法升序排列，注意这里是.sort((a, b) => a - b)。

3. 取第 k-1 个元素。

代码

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
const kthSmallest = function (matrix, k) {
  const flat = matrix.reduce((acc, item) => {
    return acc.concat(item);
  }, []).sort((a, b) => a - b);
​
  return flat[k - 1];
};

复杂度分析

• 时间复杂度：$O(n^2)$​

  reduce 执行 n 次，时间复杂度为 $O(n)$，sort 排序 $O(n^2)$, 所以时间复杂度取最大值 $O(n^2)$。

• 空间复杂度: $O(n^2)$​

  flat 的长度是 n*n，所以空间复杂度为 $O(n^2)$。

方法二

思路

1. 找出二维矩阵中最小的数left，最大的数right，那么第k小的数必定在l eft~right之间。

2. mid = (left+right) / 2；在二维矩阵中寻找小于等于 mid 的元素个数 count。

3. 若这个count小于k，表明第k小的数在右半部分且不包含mid，即left=mid+1, right=right，又保证了第k小的数在left~right之间。

4. 若这个count大于k，表明第k小的数在左半部分且可能包含mid，即left=left, right=mid，又保证了第k小的数在left~right之间。

5. 因为每次循环中都保证了第k小的数在left~right之间，当left==right时，第k小的数即被找出，等于 right。

注意：这里的 left mid right是数值，不是索引位置。

详解

1. 获取行数、列数，再取左上角的最小数、右下角最大数。

2. while循环判断left 小于 right，定义 mid = Math.floor()(left+right) / 2)；在二维矩阵中寻找小于等于mid的元素个数count。

3. 若这个count小于k，left=mid+1, right=right。

4. 若这个count大于k，即left=left, right=mid。

5. 返回right。

代码

const kthSmallest = function (matrix, k) {
  const row = matrix.length;
  const col = matrix[0].length;
  let left = matrix[0][0];
  let right = matrix[row - 1][col - 1];
​
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    const count = findNotBiggerThanMid(matrix, mid, row, col);
    if (count < k) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
​
  return right;
};
​
function findNotBiggerThanMid (matrix, mid, row, col) {
  let i = row - 1;
  let j = 0;
  let count = 0;
​
  while (i >= 0 && j < col) {
    if (matrix[i][j] <= mid) {
      count += i + 1;
      j++;
    } else {
      i--;
    }
  }
​
  return count;
}

复杂度分析

• 时间复杂度：$O(n^2)$​

  两层循环，每个最多执行 $n$ 次，时间复杂度是平方阶 $O(n^2)$。

• 空间复杂度 ：$O(1)$​

  虽然有两个循环，但没有分派多余的存储空间，所以空间复杂度为 $O(1)$。

多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

  输入: [3,2,3]
  输出: 3

示例 2：

  输入: [2,2,1,1,1,2,2]
  输出: 2

题目分析

• ⌊ n/2 ⌋ 意味着不大于 n/2 的最大正整数

  • 可以通过 Math.floor() 或 parseInt() 取得

• 最直接的想法是，遍历数组中的每个元素，如果该元素在数组中出现的次数大于 ⌊ n/2 ⌋，则将它输出。依据题目可知，在输入数组中，有且只会有 1 种数字符合输出条件，即输出的值只会有一个。该解法的重点是，如何找到该元素在数组中出现的次数。如果直接继续用循环或 filter 方法，虽然可行，但是会因时间复杂度导致运行超时。因此，需要找到合理的解决办法。

方法一 统计数量遍历求解

思路

既然两层嵌套循环会运行超时，那无脑的想法便是将循环拆开处理。第一步,先遍历数组统计各元素出现的次数，并存入对象中；第二步，找到该对象中符合题目条件的元素。话不多说，简单粗暴的方法先来一个。

详解

1、创建变量 number 和 statistics，分别用于存储结果元素和元素统计结果

2、找到“多数元素”的边界值

3、遍历并统计给定数组中各元素的出现次数，存入 statistics

4、在 statistics 中找到符合边界值要求的元素

5、return 该元素

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
const majorityElement = function (nums) {
  let number = 0;
  // statistics 元素统计结果
  const statistics = {};
  if (nums.length) {
    // 找到题目中要求的“多数元素”的边界值
    const bound = Math.floor(nums.length / 2);
    // 统计每个元素出现的次数
    nums.map((num) => {
      statistics[num] = statistics[num] ? statistics[num] + 1 : 1;
    });
    // 找到 statistics 中符合条件的元素
    Object.keys(statistics).map((key) => {
      if (statistics[key] > bound) {
        number = key;
      }
    });
  }
  return number;
};

复杂度分析

• 时间复杂度：$O(n)$​

  该解法中，两个map循环遍历总次数最多为 2n ，因此，时间复杂度为 $O(n)$。

• 空间复杂度：$O(n)$​

  该解法中，考虑到众数的频率超过 n/2，因此，statistics 的占用空间最多 n/2，空间复杂度为 $O(n)$。

方法二 双指针求解

思路

假设输入的数组为 nums=[3,1,1,2,1,3] ，我们可以考虑将其排序后，再利用两个指针查找目标值。排序后的数组如图所示，初始化时两个指针 i 和 j 分别指向数组的第一个元素（黄色箭头位置）和第二个元素（（左）红色指针位置）。

• 黄色指针 $i$ 不动，红色指针 j 每次向右移动一个格子，直到当前元素和上一元素不同时暂停，即当前停在下标为 3 的位置上。

• 此时可知元素 1 出现的次数为 j - i 次。比较该元素出现次数是否满足题目元素，若满足，则将其输出， 若不满足则继续执行下一步。

• 将黄色指针 $i$ 移动到当前指针 $j$ 的位置，如图所示。之后，继续将红色指针 $j$ 向右移动。

• 重复上述步骤，直至找到符合条件的元素

详解

1、创建变量 number，用于存储结果元素

2、对给定数组进行排序

3、找到“多数元素”的边界值

4、初始化两个指针并依据上文提到的思路进行遍历，找到出现次数大于边界值的元素

5、return 该元素

其中需考虑特殊情况，如 number 的初始值以及遍历中特殊情况的处理，详见代码。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
const majorityElement = (nums) => {
  let number = 0;
  // 数组排序
  nums.sort();
  // 为 number 赋初始值
  number = nums[0];
  if (nums.length > 1) {
    // 找到题目中要求的“多数元素”的边界值
    const bound = Math.floor(nums.length / 2);
    for (let i = 0, j = 1; j < nums.length; j += 1) {
      if (nums[i] !== nums[j]) {
        // 找到元素 i 及其出现次数
        if (j - i > bound) {
          number = nums[i];
        } else {
          // 若不满足条件则移动 i 指针至当前 j 指针的位置
          i = j;
        }
      }
      // 若指针 j 已经移动到最后一个元素位置时，仍未找到满足条件的元素，则当前元素为最终结果
      if (j === nums.length - 1) {
        number = nums[i];
      }
    }
  }
  return number;
};

复杂度分析

• 时间复杂度：$O(nlogn)$​

  上述解法中，使用了 sort() 方法，该方法在底层实现上依不同浏览器而有所差异。在 Chrome 浏览器中，使用了插入排序和快速排序结合的算法，具体使用情况与待排序数组的长度有关，一般情况下长度小于等于 10 的数组使用插入排序（可参考：深入浅出 JavaScript 的 Array.prototype.sort 排序算法）。假设此处考虑 Chrome 浏览器下使用快排作为排序算法的情况，则 sort() 耗时为 $O(nlogn)$。排序后 for 循环耗时 $O(n)$。因此，时间复杂度可记为 $O(nlogn)$，其最差可能为 $O(n^2)$。

• 空间复杂度：$O(logn)$​

  该解法中，自主申请的变量为常量级别 $O(1)$。sort() 使用插入排序时空间复杂度为 $O(1)$，使用快排时为 $O(logn)$。因此空间复杂度最好为 $O(1)$，最差为 $O(logn)$。（此分析仅以 Chrome 浏览器为例，其余浏览器的情况可具体分析）

方法三 Boyer-Moore Vote Algorithm

思路

​摩尔投票算法（多数投票算法），该算法由 Robert S.Boyer 和 J Strother Moore 发明，它可以高效的计算出序列中哪个元素占多数。

同样利用两个指针，初始时分别位于第一个元素和第二个元素位置。假定 count = 1，数组的每一轮遍历中，判断两个指针所指元素是否相等，若相等则 count++，否则 count--。若此时 count === 0，意味着相邻两元素值不相同，需将两指针分别向前移动一位并将 count 还原为初始值。

详解

1、初始化指针 majorityIndex 和 count 的值分别为 0 和 1

2、遍历给定数组，判断相邻两元素是否相等并依据判断结果修改 count 的值。若此时 count 为 0，则将 majorityIndex 指针移动到当前 i 指针的位置，并重新将 count 设置为 1

3、return 给定数组中下标为 majorityIndex 的元素

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
const majorityElement = (nums) => {
  // 指针，指向符合输出条件的元素
  let majorityIndex = 0;
  // 计数器
  let count = 1;
  for (let i = 1; i < nums.length; i += 1) {
    // 判断相邻两元素是否相等
    nums[majorityIndex] === nums[i] ? count += 1 : count -= 1;
    if (count === 0) {
      majorityIndex = i;
      count = 1;
    }
  }
  return nums[majorityIndex];
};

复杂度分析

• 时间复杂度：$O(n)$​

  该解法中，只需要遍历一次数组，其时间复杂度为 $O(n)$。

• 空间复杂度：$O(1)$​

  该解法中，仅申请了 2 个常量级的额外空间，因此空间复杂度为 $O(1)$。