前 K 个高频元素、寻找峰值和合并区间
前 K 个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
1
输入: nums = [1,1,1,2,2,3], k = 2
2
输出: [1,2]
Copied!
示例 2:
1
输入: nums = [1], k = 1
2
输出: [1]
Copied!
说明：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
方法一
思路
这一题属于比较简单的算法题，整体的思路是需要开辟一个新的储存空间，对数组中数字的出现的次数进行记录，再对这个存储记录进行读取，进而得出前 K 个高频元素
详解
第一步，记录每个数出现的次数
1
let map = new Map();
2
for (let num of nums) { // 记录每个数出现的次数
3
map.set(num, (map.get(num) || 0) + 1);
4
}
Copied!
第二步，设置一个数组 countOfNum，其第 i 个元素表示出现 i 次的元素数组
1
let countOfNum = Array(nums.length);
2
for (let key of map.keys()) {
3
let value = map.get(key);
4
if (countOfNum[value] === undefined) {
5
countOfNum[value] = [key]
6
} else {
7
countOfNum[value].push(key)
8
}
9
}
Copied!
第三步，从 countOfNum 末尾开始往头遍历，将非空元素都加入结果数组中，直到结果数组的大小等于K。
1
let res = [];
2
for (let i = countOfNum.length - 1; i >= 0 && res.length < k; i--) {
3
if (countOfNum[i] !== undefined) {
4
res = res.concat(countOfNum[i])
5
}
6
}
7
return res;
Copied!
代码
1
/**
2
* @param {number[]} nums
3
* @param {number} k
4
* @return {number[]}
5
*/
6
const topKFrequent = function(nums, k) {
7
let map = new Map();
8
for (let num of nums) {
9
map.set(num, (map.get(num) || 0) + 1);
10
}
11
12
let countOfNum = Array(nums.length);
13
for (let key of map.keys()) {
14
let value = map.get(key);
15
if (countOfNum[value] === undefined) {
16
countOfNum[value] = [key]
17
} else {
18
countOfNum[value].push(key)
19
}
20
}
21
22
let res = [];
23
for (let i = countOfNum.length - 1; i >= 0 && res.length < k; i--) {
24
if (countOfNum[i] !== undefined) {
25
res = res.concat(countOfNum[i])
26
}
27
}
28
return res;
29
};
Copied!
复杂度分析
- 时间复杂度：
- 上述解法中，我们使用了一层 for 循环，里面的代码会执行 n 遍，它消耗的时间是随着 n 的变化而变化的，因此时间复杂度是
- 空间复杂度:
- 上述解法中，我们额外声明的空间大小和输入规模成正比，所以空间复杂度为
方法二
思路
整体思路同方法一，这一种方法我们使用 forEach 和 sort 简化了实现方案
详解
第一步，构建一个对象作为储存空间
1
const hashTable = {}
2
nums.forEach(item => {
3
if (hashTable[item] === undefined) {
4
hashTable[item] = 1
5
} else {
6
hashTable[item]++
7
}
8
})
Copied!
第二步，根据存储的出现次数，对数组进行排序
1
hashTableArray = Object.keys(hashTable)
2
hashTableArray.sort((prev, next) => {
3
return hashTable[next] - hashTable[prev]
4
})
Copied!
第三步，截取数去的前K项，得到想要的结果
1
return hashTableArray.slice(0, k)
Copied!
代码
1
/**
2
* @param {number[]} nums
3
* @param {number} k
4
* @return {number[]}
5
*/
6
var topKFrequent = function(nums, k) {
7
const hashTable = {}
8
nums.forEach(item => {
9
if (hashTable[item] === undefined) {
10
hashTable[item] = 1
11
} else {
12
hashTable[item]++
13
}
14
})
15
hashTableArray = Object.keys(hashTable)
16
hashTableArray.sort((prev, next) => {
17
return hashTable[next] - hashTable[prev]
18
})
19
return hashTableArray.slice(0, k)
20
};
Copied!
复杂度分析
- 时间复杂度：
- 空间复杂度:
寻找峰值
峰值元素是指其值大于左右相邻值的元素。 给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。 数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞。
示例
1
输入: nums = [1,2,3,1]
2
输出: 2
3
解释: 3 是峰值元素，你的函数应该返回其索引 2。
Copied!
方法一 取最大值
思路
取最大值法思路最简单，最大值必然就是其峰值。因为这是算法题，我们就不用 Math.max 了。直接一次循环解决问题。
详解
- 1.使用数组的 reduce 方法遍历数组，设其初始值为 0。
- 2.当遍历到的值大于上一次返回的下标所对应的值时返回当前下标。
- 3.遍历结束后所获取的值为最终答案。
代码
1
const findPeakElement = function (nums) {
2
return nums.reduce((index, cur, i) => {
3
if (nums[index] < cur) {
4
return i;
5
}
6
return index;
7
}, 0);
8
};
Copied!
复杂度分析
- 时间复杂度：对于每个元素，通过遍历数组进行比较值的大小来寻找它所对应的目标元素，这将耗费的时间。
- 空间复杂度：算法执行的过程中，声明的变量并不与数组的长度相关。故而空间复杂度为。
方法二 暴力法
思路
暴力法很简单，遍历每个元素，并寻找到元素 n 大于元素 n + 1。则 n 就是我们要找的峰值。如果没有这个值，则数组的最后一个元素就是峰值。
详解
- 1.遍历数组找出第 i 个元素大于 i+1 个元素的元素的下标为结果。
- 2.如果遍历完成没有找到，则取元素最后一个值的下标为结果。
代码
1
const findPeakElement = function (nums) {
2
// 如果全部从小到大排列，则峰值为最后一个元素
3
let result = nums.length - 1;
4
// 否则只要找出第 i 个元素大于 i+1 个元素，则第 i 个元素就是峰值
5
for (let i = 0; i < nums.length - 1; i += 1) {
6
if (nums[i] > nums[i + 1]) {
7
result = i;
8
break;
9
}
10
}
11
return result;
12
};
Copied!
复杂度分析
- 时间复杂度：对于每个元素，通过遍历数组进行比较值的大小来寻找它所对应的目标元素，这将耗费的时间。
- 空间复杂度：算法执行的过程中，声明的变量并不与数组的长度相关。故而空间复杂度为。
方法三 二分法
思路
将数组从中间分成两个数组 L 和 R。比较 L 最后一个值 l 与 R 的第一个值 r 的大小。如果 l > r 则数组 L 必有一个及以上原数组的峰值，取数组 L 再做上一步。反之则数组 R 必有一个及以上原数组的峰值，取数组 R 再做上一步。当数组长度为 1 时。其值为峰值。
详解
- 1.将目标数组从中间分成两个数组 L 和 R。
- 2.比较 L 最后一个值 l 与 R 的第一个值 r 的大小。
- 3.如果 l > r 则数组 L 必有一个及以上原数组的峰值，取数组 L 作为目标数组。
- 4.反之则数组 R 必有一个及以上原数组的峰值，取数组 R 作为目标数组。
- 5.目标数组长度为 1 则其值为峰值。
- 6.目标数组长度大于 1 则重复 1，2，3，4 步骤。直至目标数组长度为 1 为止。
代码
1
const findPeakElement = function (nums) {
2
let lIndex = 0; // 虚拟数组第一个元素下标
3
let rIndex = nums.length - 1; // 虚拟数组最后一个元素下标
4
let mid; // 数组中间元素下标。
5
while (lIndex < rIndex) { // 当数组长度不为 1 时。
6
mid = Math.floor((lIndex + rIndex) / 2); // 取当前虚拟数组的中间元素的下标（当数组长度为偶数时取小的那个），可将虚拟元素隔开成两个数组。
7
if (nums[mid] > nums[mid + 1]) { // 比较左边数组最后一个元素与右边数组的第一个元素的大小
8
rIndex = mid; // 左边数组最后一个元素大、则取左边数组
9
} else {
10
lIndex = mid + 1; // 右边数组第一个元素大、则取右边数组
11
}
12
}
13
return lIndex;
14
};
Copied!
复杂度分析：
- 时间复杂度：每次循环数组的长度都除以 2 。设 x 次循环之后。也就是说 2 的 x 次方等于 n，那么。也就是说当循环 log2^n 次以后，代码运行结束。因此这个代码的时间复杂度为：。
- 空间复杂度：算法执行的过程中，声明的变量并不与数组的长度 n 相关。故而空间复杂度为 O(1)。
合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例
1
输入: [[1,3],[2,6],[8,10],[15,18]],
2
输出: [[1,6],[8,10],[15,18]]。
3
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
Copied!
方法一 合并重叠
思路：
从示例入手： 1.[1, 3] [2, 6] 是否可以合并只要对比 [1, 3]的最大值 3，[2, 6]的最小值 2，3 <= 2 ，则说明可以合并，否则不能。 2.[1, 3] [2, 6] [8,10]，从3个来看，如果 [2, 6]的最大值6 <= [8,10]的最小值 8，则说明[2, 6] 不能和 [8,10]，因此 [1, 3] [2, 6] 执行合并操作，[8,10] 继续与下一个数组执行步骤一。
详解：
1
1.对区间进行排序（升序）
2
2.从第一区间起取当前拟合并区间为a，
3
3.取下一区间为b（如果没有b了则输出a，退出）
4
4.如果a的尾 > b 的头 ,则合并为 a，否则输出a，把b作为a。
Copied!
1
const merge = intervals => {
2
intervals.sort((a, b) => {
3
if (a[0] !== b[0]){
4
return a[0] - b[0];
5
}
6
return a[1] - b[1];
7
});
8
let len = intervals.length,
9
ans = [], // 定义新数组
10
start, end; // 遍历当前区间的最小值与最大值
11
for (let i = 0; i < len; i++) {
12
let s = intervals[i][0],
13
e = intervals[i][1];
14
if (start === undefined){
15
start = s, end = e;
16
} else if (s <= end){
17
end = Math.max(e, end);
18
} else {
19
let part = [start, end];
20
ans.push(part);
21
start = s;
22
end = e;
23
}
24
}
25
if (start !== undefined) {
26
let part = [start, end];
27
ans.push(part);
28
}
29
return ans;
30
};
Copied!
复杂度分析
- 时间复杂度：
- 空间复杂度：
方法二 合并重叠
思路
从示例入手： 1.申明一个变量用于存储合并的结果 res = [] 2.第一个数组直接放入res中，res = [[1, 3]] 3.对比 res中的 [1, 3] 和 下一个数组 [2 ,6]，[1,3] 的最大值 3 <= [2, 6] 的最小值2，则 res = [[1, 6]] 4.继续对比 res中的 [1, 6] 和下一个数组 [8, 10]，则 res = [[1, 6], [8, 10]] 5.然后 从 [8, 10] 开始 继续执行步骤三
详解
- 1.对区间进行排序（升序）
- 2.定义一个新的数组，用于存储新的数组区间。
- 3.从第二个值开始遍历原数组，比较当前区间的最小值是否大于新数组最后一个区间的最大值，如果满足则push进入新的数组；又或者比较当前区间的最大值是否大于新新数组的随后一个区间的最大值，若满足则将新数组的最后一个区间的最大值替换成当前区间的最大值。
1
const merge = function(intervals) {
2
if (!intervals || intervals.length === 0) {
3
return [];
4
}
5
let input = intervals.sort((a, b) => a[0] - b[0]);
6
let res = [];
7
res.push(input[0]);
8
for(let i = 1, len = input.length; i < len; i++) {
9
if (input[i][0] > res[res.length - 1][1]) {
10
res.push(input[i]);
11
} else if (input[i][1] > res[res.length - 1][1]){
12
res[res.length - 1][1] = input[i][1];
13
}
14
}
15
return res;
16
};
Copied!
复杂度分析
- 时间复杂度：该算法对含有 n 个结点的列表进行了一次遍历。因此时间复杂度为。
- 空间复杂度：该算法只开辟了额外空间用于存储结果，空间大小与数组长度n成正比。故空间复杂度为。