LeetCode算法问题14 —— Kth Largest Element in an Array
程序员文章站
2022-04-25 13:25:11
...
首先看下问题描述
题目要求给一个无序数组,要求找到第k大的数。
最先想到的办法自然是通过排序先获得一个有序数组,再通过提取对应位置获得结果,例如,可通过库函数sort来解答问题:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
然而我想了另外一个方法:通过维护一个长度为k的数组temp,保证temp有序,其中temp是按从大到小顺序排列的,在遍历过一次给定数组后,只需取出temp最后一个数即可。遍历给定数组过程中
对于数组temp,会出现三种情况:
- 1:temp还没有任何数
此时把遍历到的数加入temp即可
- 2:temp有数但还未满
此时需要首先从temp最大的数开始遍历,找到第一个比nums[i]小的数,由于temp还未满,因此可以把它们都向后移,实际上就是将nums[i]插进去,如果没找到就放在最后
- 3:temp已满
此时要对temp数组遍历,找到第一个比nums[i]小的,然后插进去,因此后面的数据也会向后移动一个,与情况2不同,此时temp已经满了,因此之前最后一个数据实际上是被抛弃了
全代码如下:
int findKthLargest(vector<int>& nums, int k) {
int* temp = new int[k];
int size = 0;
for (int i = 0; i < nums.size(); i++) {
if (size == 0) {
temp[0] = nums[i];
size++;
} else if (size < k) {
for (int j = 0; j < size; j++) {
if (temp[j] < nums[i]) {
for (int n = size - 1; n > j - 1; n--) {
temp[n + 1] = temp[n];
}
temp[j] = nums[i];
size++;
break;
}
if (j == size - 1) {
temp[j + 1] = nums[i];
size++;
break;
}
}
} else if (size == k) {
for (int j = 0; j < size; j++)
if (temp[j] < nums[i]) {
for (int n = size - 1; n > j - 1; n--) {
temp[n + 1] = temp[n];
}
temp[j] = nums[i];
break;
}
}
}
return temp[k - 1];
delete temp;
}
推荐阅读
-
Kth Largest Element in an Array Leetcode #215 题解[C++]
-
LeetCode 215 Kth Largest Element in an Array
-
LeetCode 215. Kth Largest Element in an Array
-
LeetCode算法问题14 —— Kth Largest Element in an Array
-
215. Kth Largest Element in an Array(返回数组中第几大元素)(leetcode)
-
LeetCode 215 -- 数组中的第K个最大元素 ( Kth Largest Element in an Array ) ( C语言版 )
-
leetcode215:Kth Largest Element in an Array
-
LeetCode------Kth Largest Element in an Array
-
【Leetcode】Kth Largest Element in an Array