215. 数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例：[3,2,1,5,6,4] 和 k = 2 => 5 ； [3,2,3,1,2,4,5,5,6] 和 k = 4 => 4
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
- 1、自己写的算法，利用数组的
sort直接处理
时间复杂度：O(n)，空间复杂度：xx
var findKthLargest = function (nums, k) {
let res = nums.sort((a, b) => {
if (a < b) {
return 1;
} else if (a == b) {
return 0;
} else {
return -1;
}
});
return res[k - 1];
};
- 2、冒泡算法
时间复杂度：O(n^2)，空间复杂度：xx
var findKthLargest = function (nums, k) {
// i 要少一个
for(let i = 0; i < nums.length - 1; i++) {
let tag = true;
for(let j = i+1; j < nums.length; j = j+1) {
// 较小的那位交换往后冒泡
if(nums[i] < nums[j]) {
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
tag = false;
}
}
if(tag) {
break
}
}
return nums[k - 1];
};
- 3、冒泡算法优化 - 找到第k个值就退出
利用题目找寻的是第k个值，将外部循环控制在k次
时间复杂度：O(n^2)，空间复杂度：xx
var findKthLargest = (nums, k) => {
// 循环 k 次，只排序到第 k 个大的值
for(let i = 0; i < k ; i++) {
let tag = true;
// 得从后往前，把大值的往前送
for (let j = nums.length - 1; j >= 0; j--) {
// 前面小于后面，则交换 -> 将值从大往小排
if(nums[j] < nums[j + 1]) {
let temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
tag = false;
}
}
if(tag) {
break
}
}
return nums[k - 1];
}
- 4、插入排序
时间复杂度：O(n^2)，空间复杂度：xx
var findKthLargest = (nums, k) => {
// 外层循环的是循环次数
for (var i = 1; i < nums.length; i++) {
// 里层循环的是 大 -> 小
for (var j = i; j > 0; --j) {
if (nums[j - 1] < nums[j]) {
// 前一项小于后一项，则交换
[nums[j - 1], nums[j]] = [nums[j], nums[j - 1]];
}
}
}
return nums[k - 1];
}
- 5、插入排序 - 优化
在 i 第一次比较不需要交换时，不需要再执行当前内层循环 -> 数组小于 i 的部分已经是有序数组了
时间复杂度：O(n^2)，空间复杂度：xx
var findKthLargest = (nums, k) => {
for (var i = 1; i < nums.length; i++) {
// 优化
if (nums[i-1] > nums[i]) {
continue;
}
for (var j = i; j > 0; --j) {
if (nums[j - 1] < nums[j]) {
[nums[j - 1], nums[j]] = [nums[j], nums[j - 1]];
}
}
}
return nums[k - 1];
}
- 6、快速排序
时间复杂度：O(n^2)，空间复杂度：xx
var findKthLargest = (nums, k) => {
var quickSort = function (arr) {
// 退出递归的条件
if (arr.length <= 1) {
return arr;
}
var midIndex = Math.floor(arr.length / 2);
// 从原数组中拿出 mid 值
var mid = arr.splice(midIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
// 根据 mid 值，将原数组划分成两半
if (arr[i] > mid) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// 递归 - 左半部分 + mid + 右半部分
return quickSort(left).concat([mid], quickSort(right));
};
let res = quickSort(nums);
return res[k - 1];
}