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)O(time)

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

  • 空间复杂度:O(1)O(1)

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

方法二 桶思想

思路

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

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

可以得到结果为 (n+1)(count1)+(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)O(n)

    nn 为任务的总数

  • 空间复杂度:O(1)O(1)

    与 n 无关,申请数组的长度最大为26,复杂度为 O(1)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(n2)O(n^2)

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

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

    flat 的长度是 n*n,所以空间复杂度为 O(n2)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(n2)O(n^2)

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

  • 空间复杂度 :O(1)O(1)

    虽然有两个循环,但没有分派多余的存储空间,所以空间复杂度为 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、创建变量 numberstatistics,分别用于存储结果元素和元素统计结果

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)O(n)

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

  • 空间复杂度:O(n)O(n)

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

方法二 双指针求解

思路

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

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

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

  • 将黄色指针 ii 移动到当前指针 jj 的位置,如图所示。之后,继续将红色指针 jj 向右移动。

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

详解

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)O(nlogn)

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

  • 空间复杂度:O(logn)O(logn)

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

方法三 Boyer-Moore Vote Algorithm

思路

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

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

详解

1、初始化指针 majorityIndexcount 的值分别为 01

2、遍历给定数组,判断相邻两元素是否相等并依据判断结果修改 count 的值。若此时 count0,则将 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(n)O(n)

  • 空间复杂度:O(1)O(1)

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