215. Kth Largest Element in an Array
文章目录
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
难度:medium
题目:找出在没有排序的数组中第K大的元素,注意是排序后的第K大的元素,不是第K个不同元素。
思路:快速排序
Runtime: 29 ms, faster than 36.08% of Java online submissions for Kth Largest Element in an Array.
Memory Usage: 38.8 MB, less than 51.09% of Java online submissions for Kth Largest Element in an Array.
class Solution {
public int findKthLargest(int[] nums, int k) {
int idx = -1;
k = nums.length - k;
for (int i = 0, j = nums.length - 1; i <= j && idx != k;) {
idx = quickSort(nums, i, j);
if (idx < k) {
i = idx + 1;
} else if (idx > k) {
j = idx - 1;
}
}
return nums[idx];
}
private int quickSort(int[] nums, int i, int j) {
int piovt = nums[i];
while (i < j) {
while (i < j && nums[j] >= piovt) {
j--;
}
nums[i] = nums[j];
while (i < j && nums[i] < piovt) {
i++;
}
nums[j] = nums[i];
}
nums[i] = piovt;
return i;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论