算法:数组中的第 K 个最大元素
算法 About 1,277 words题目
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
可以假设k
总是有效的,且1 ≤ k ≤ array.length
。
示例一
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例二
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
思路
数组排序后取第array.length - k
个。
实现
方法一
冒泡排序:增加计数count
,当排了k
次序后,已经末尾k
个元素已经有序,直接跳出循环,取末尾第k
个;增加标志位flag
,当轮询一次后都没有发生元素交换,说明已经有序,直接跳出循环,取末尾第k
个。
public int findKthLargest(int[] arr, int k) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
boolean flag = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
// 一次都没交换,说明已经有序
if (!flag) {
break;
}
// 第k次排序后,末尾的几个元素已经有序
count++;
if (count >= k) {
break;
}
}
return arr[arr.length - k];
}
执行用时:49 ms
, 在所有Java
提交中击败了5.68%
的用户
内存消耗:38.9 MB
, 在所有Java
提交中击败了26.97%
的用户
方法二
直接调用Java
工具类。- -!
public int findKthLargest(int[] arr, int k) {
Arrays.sort(arr);
return arr[arr.length - k];
}
执行用时:2 ms
, 在所有Java
提交中击败了90.42%
的用户
内存消耗:38.7 MB
, 在所有Java
提交中击败了71.80%
的用户
LeetCode 原题地址
https://leetcode-cn.com/problems/kth-largest-element-in-an-array
Views: 1,445 · Posted: 2021-02-23
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...