Task Sheduler、有序矩阵中第K小的元素和多数元素
Task Scheduler
给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的 26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的最短时间。
示例
1
输入: tasks = ["A","A","A","B","B","B"], n = 2
2
输出: 8
3
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
Copied!
方法一 贪心选择法
思路
每一轮选择尽可能多的不超过 n + 1 个任务执行，直到所有的任务被执行完。
详解
- 1.对任务按照剩余的次数进行降序排序，从剩余次数最多的任务开始依次来执行
- 2.每次判断任务是否可以执行，如果可以把对剩余的任务数量 -1
- 3.一轮跑完之后，要重新对任务进行排列，保证任务的排序是降序
1
const leastInterval = function (tasks, n) {
2
const counts = Array(26).fill(0);
3
tasks.forEach(v => {
4
const index = v.charCodeAt() - 65; // 'A'.charCodeAt() 为 65
5
counts[index]++;
6
});
7
counts.sort((a, b) => (b - a)); // 直接从大到小排
8
let res = 0;
9
while (counts[0] > 0) {
10
let i = 0;
11
while (i < n + 1) { // 保证这一轮任务距离上次执行至少冷却 n 个单位的时间
12
if (counts[0] === 0) { // 当最大当任务数为 0，跳出循环
13
break;
14
}
15
if (i < 26 && counts[i] > 0) { // 判断任务是否可以执行
16
counts[i]--;
17
}
18
res++;
19
i++;
20
}
21
counts.sort((a, b) => (b - a)); // 每次任务执行完，保证最多的任务排在最前面
22
}
23
return res;
24
};
Copied!
复杂度分析
- 时间复杂度：通过我们发现，最终的时间为多少，时间复杂度就是多少，这种解法的缺点在于，得出相当于是把每个任务执行了一遍
- 空间复杂度：与 n 无关，申请数组的长度最大为26，复杂度为
方法二 桶思想
思路
换一种形象的比喻，把间隔时间必做桶。
每个桶固定大小为 n + 1，最后一个除外，把相同的任务分在不同的桶中，那么桶的数量就由数量最多的任务的数量来决定
可以得到结果为
，至于说最后一个桶对任务数是多少，通过找规律发现，即为有多少个最多任务数
比如
["A","A","A","B","B","B"]，即为 2，因为 A 和 B 的数量最多且一样还有一种情况，当没有出现等待时，比如
["A", "A", "B", "C", "D"]，间隔 n = 2 的时候，此时最小时间就是任务的长度明显是 4但是发现上面的公式得出的值为1，不对了，此时我们只需要取两个数的最大值就可以了
详解
1、将任务按类型分组，把字母转为数字做数组的索引存在数组里
2、对数组进行排序，找出上面公式的 count 和 最后一个桶的任务数
3、最后套公式就可以得出答案了
1
const leastInterval = function (tasks, n) {
2
const counts = Array(26).fill(0);
3
tasks.forEach(v => {
4
const index = v.charCodeAt() - 65; // 'A'.charCodeAt() 为 65
5
counts[index]++;
6
});
7
counts.sort((a, b) => (b - a)); // 直接从大到小排
8
const max = counts[0];
9
const maxCount = counts.filter(a => a === max).length; // 多少个最多任务数
10
const res = (n + 1) * (max - 1) + maxCount;
11
return res > tasks.length ? res : tasks.length;
12
};
Copied!
复杂度分析：
- 时间复杂度：为任务的总数
- 空间复杂度：与 n 无关，申请数组的长度最大为26，复杂度为
有序矩阵中第K小的元素
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。 请注意，它是排序后的第k小元素，而不是第k个元素。
示例
1
matrix = [
2
[ 1, 5, 9],
3
[10, 11, 13],
4
[12, 13, 15]
5
],
6
k = 8,
7
8
返回 13。
Copied!
说明 你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。
方法一
思路
将二维数组展开为一维升序数组，取第 k-1 位。
详解
- 1.将数组使用reduce展开为一维数组。
- 2.使用数组的sort方法升序排列，注意这里是
.sort((a, b) => a - b)。 - 3.取第 k-1 个元素。
代码
1
/**
2
* @param {number[][]} matrix
3
* @param {number} k
4
* @return {number}
5
*/
6
const kthSmallest = function (matrix, k) {
7
const flat = matrix.reduce((acc, item) => {
8
return acc.concat(item);
9
}, []).sort((a, b) => a - b);
10
11
return flat[k - 1];
12
};
Copied!
复杂度分析
- 时间复杂度：reduce 执行 n 次，时间复杂度为，sort 排序, 所以时间复杂度取最大值。
- 空间复杂度:flat 的长度是 n*n，所以空间复杂度为。
方法二
思路
- 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。
代码
1
const kthSmallest = function (matrix, k) {
2
const row = matrix.length;
3
const col = matrix[0].length;
4
let left = matrix[0][0];
5
let right = matrix[row - 1][col - 1];
6
7
while (left < right) {
8
const mid = Math.floor((left + right) / 2);
9
const count = findNotBiggerThanMid(matrix, mid, row, col);
10
if (count < k) {
11
left = mid + 1;
12
} else {
13
right = mid;
14
}
15
}
16
17
return right;
18
};
19
20
function findNotBiggerThanMid (matrix, mid, row, col) {
21
let i = row - 1;
22
let j = 0;
23
let count = 0;
24
25
while (i >= 0 && j < col) {
26
if (matrix[i][j] <= mid) {
27
count += i + 1;
28
j++;
29
} else {
30
i--;
31
}
32
}
33
34
return count;
35
}
Copied!
复杂度分析
- 时间复杂度：两层循环，每个最多执行次，时间复杂度是平方阶。
- 空间复杂度 ：虽然有两个循环，但没有分派多余的存储空间，所以空间复杂度为。
多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于
⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
1
输入: [3,2,3]
2
输出: 3
Copied!
示例 2：
1
输入: [2,2,1,1,1,2,2]
2
输出: 2
Copied!
题目分析
⌊ n/2 ⌋意味着不大于n/2的最大正整数- 可以通过
Math.floor()或parseInt()取得
- 最直接的想法是，遍历数组中的每个元素，如果该元素在数组中出现的次数大于
⌊ n/2 ⌋，则将它输出。依据题目可知，在输入数组中，有且只会有 1 种数字符合输出条件，即输出的值只会有一个。该解法的重点是，如何找到该元素在数组中出现的次数。如果直接继续用循环或filter方法，虽然可行，但是会因时间复杂度导致运行超时。因此，需要找到合理的解决办法。
方法一 统计数量遍历求解
思路
既然两层嵌套循环会运行超时，那无脑的想法便是将循环拆开处理。第一步,先遍历数组统计各元素出现的次数，并存入对象中；第二步，找到该对象中符合题目条件的元素。话不多说，简单粗暴的方法先来一个。
详解
1、创建变量
number 和 statistics，分别用于存储结果元素和元素统计结果2、找到“多数元素”的边界值
3、遍历并统计给定数组中各元素的出现次数，存入
statistics4、在
statistics 中找到符合边界值要求的元素5、return 该元素
代码
1
/**
2
* @param {number[]} nums
3
* @return {number}
4
*/
5
const majorityElement = function (nums) {
6
let number = 0;
7
// statistics 元素统计结果
8
const statistics = {};
9
if (nums.length) {
10
// 找到题目中要求的“多数元素”的边界值
11
const bound = Math.floor(nums.length / 2);
12
// 统计每个元素出现的次数
13
nums.map((num) => {
14
statistics[num] = statistics[num] ? statistics[num] + 1 : 1;
15
});
16
// 找到 statistics 中符合条件的元素
17
Object.keys(statistics).map((key) => {
18
if (statistics[key] > bound) {
19
number = key;
20
}
21
});
22
}
23
return number;
24
};
Copied!
复杂度分析
- 时间复杂度：该解法中，两个map循环遍历总次数最多为
2n，因此，时间复杂度为。 - 空间复杂度：该解法中，考虑到众数的频率超过
n/2，因此，statistics的占用空间最多n/2，空间复杂度为。
方法二 双指针求解
思路
假设输入的数组为
nums=[3,1,1,2,1,3] ，我们可以考虑将其排序后，再利用两个指针查找目标值。排序后的数组如图所示，初始化时两个指针 i 和 j 分别指向数组的第一个元素（黄色箭头位置）和第二个元素（（左）红色指针位置）。- 黄色指针不动，红色指针 j 每次向右移动一个格子，直到当前元素和上一元素不同时暂停，即当前停在下标为 3 的位置上。
- 此时可知元素 1 出现的次数为
j - i次。比较该元素出现次数是否满足题目元素，若满足，则将其输出， 若不满足则继续执行下一步。
- 将黄色指针移动到当前指针的位置，如图所示。之后，继续将红色指针向右移动。
- 重复上述步骤，直至找到符合条件的元素
详解
1、创建变量
number，用于存储结果元素2、对给定数组进行排序
3、找到“多数元素”的边界值
4、初始化两个指针并依据上文提到的思路进行遍历，找到出现次数大于边界值的元素
5、return 该元素
其中需考虑特殊情况，如number的初始值以及遍历中特殊情况的处理，详见代码。
代码
1
/**
2
* @param {number[]} nums
3
* @return {number}
4
*/
5
const majorityElement = (nums) => {
6
let number = 0;
7
// 数组排序
8
nums.sort();
9
// 为 number 赋初始值
10
number = nums[0];
11
if (nums.length > 1) {
12
// 找到题目中要求的“多数元素”的边界值
13
const bound = Math.floor(nums.length / 2);
14
for (let i = 0, j = 1; j < nums.length; j += 1) {
15
if (nums[i] !== nums[j]) {
16
// 找到元素 i 及其出现次数
17
if (j - i > bound) {
18
number = nums[i];
19
} else {
20
// 若不满足条件则移动 i 指针至当前 j 指针的位置
21
i = j;
22
}
23
}
24
// 若指针 j 已经移动到最后一个元素位置时，仍未找到满足条件的元素，则当前元素为最终结果
25
if (j === nums.length - 1) {
26
number = nums[i];
27
}
28
}
29
}
30
return number;
31
};
Copied!
复杂度分析
- 时间复杂度：上述解法中，使用了
sort()方法，该方法在底层实现上依不同浏览器而有所差异。在 Chrome 浏览器中，使用了插入排序和快速排序结合的算法，具体使用情况与待排序数组的长度有关，一般情况下长度小于等于 10 的数组使用插入排序（可参考：深入浅出 JavaScript 的 Array.prototype.sort 排序算法）。假设此处考虑 Chrome 浏览器下使用快排作为排序算法的情况，则sort()耗时为。排序后for循环耗时。因此，时间复杂度可记为，其最差可能为。 - 空间复杂度：该解法中，自主申请的变量为常量级别。
sort()使用插入排序时空间复杂度为，使用快排时为。因此空间复杂度最好为，最差为。（此分析仅以 Chrome 浏览器为例，其余浏览器的情况可具体分析）
方法三 Boyer-Moore Vote Algorithm
思路
同样利用两个指针，初始时分别位于第一个元素和第二个元素位置。假定
count = 1，数组的每一轮遍历中，判断两个指针所指元素是否相等，若相等则 count++，否则 count--。若此时 count === 0，意味着相邻两元素值不相同，需将两指针分别向前移动一位并将 count 还原为初始值。详解
1、初始化指针
majorityIndex 和 count 的值分别为 0 和 12、遍历给定数组，判断相邻两元素是否相等并依据判断结果修改
count 的值。若此时 count 为 0，则将 majorityIndex 指针移动到当前 i 指针的位置，并重新将 count 设置为 13、return 给定数组中下标为
majorityIndex 的元素代码
1
/**
2
* @param {number[]} nums
3
* @return {number}
4
*/
5
const majorityElement = (nums) => {
6
// 指针，指向符合输出条件的元素
7
let majorityIndex = 0;
8
// 计数器
9
let count = 1;
10
for (let i = 1; i < nums.length; i += 1) {
11
// 判断相邻两元素是否相等
12
nums[majorityIndex] === nums[i] ? count += 1 : count -= 1;
13
if (count === 0) {
14
majorityIndex = i;
15
count = 1;
16
}
17
}
18
return nums[majorityIndex];
19
};
Copied!
复杂度分析
- 时间复杂度：该解法中，只需要遍历一次数组，其时间复杂度为。
- 空间复杂度：该解法中，仅申请了 2 个常量级的额外空间，因此空间复杂度为。
最近更新 1yr ago