题目描述
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
题解
根据问题的描述其实我们很容易想到先排序再取第k个值， 这种方式也就是我们俗称的暴力求解法。
暴力求解法
思路分析：
数组排序后的第k个最大元素，举例说明一下：
数组一共有5个元素时，找第2大，索引值是3；找第4大，索引值是1；根据这个逻辑我们可以推导出，数组升序排序以后，结果元素的索引值是数组长度减去k的值。
代码示例：
public static int findKthLargest(int[] nums, int k) {
int len = nums.length;
Arrays.sort(nums);
return nums[len - k];
}
复杂度分析：
- 时间复杂度：O(N log N), 这里直接使用Arrays.sort(nums);将数据排序，大家都知道jdk默认使用的是快速排序，快速排序的平均时间复杂度是O(N log N)。
- 空间复杂度：O(1)，因为是原地排序，没有用到外部辅助空间。
暴力求解法（升级版）
思路分析：
根据暴力求解法中用的快排思路，其实我可以对快排做近一步升级，首先我们随机选择一个元素，并在线性时间内找到其对应在数组中的位置，这样数组就被分成了两部分，一部分是小于元素值的部分，一部分是大于元素值的部分，这时我们在比较这个元素与k的大小来决定我们在那一部分数组继续做快速排序。这种思路其实就是快速排序中partition（切分）的操作。
每次partition操作总能排定一个元素，还能够知道这个元素它在数组中的最终位置，然后我们在根据partition后的结果来减少范围，这样的思想叫做“减而治之”。
代码示例：
public static int findKthLargest(int[] nums, int k) {
int leng = nums.length;
int left = 0;
int right = leng - 1;
int target = leng - k;
return quickSelect(nums, left, right, target);
}
/**
* 排序
* @param nums
* @param left
* @param right
* @param target
* @return
*/
public static int quickSelect(int[] nums, int left, int right, int target) {
if (left == right) {
return nums[left];
}
//随机选择一个
Random random = new Random();
int pivot = left + random.nextInt(right - left);
pivot = partition(nums, left, right, pivot);
if (target == pivot) {
return nums[target];
}
if (target < pivot) {
return quickSelect(nums, left, pivot - 1, target);
}
return quickSelect(nums, pivot + 1, right, target);
}
/**
* partition切分
* @param nums
* @param left
* @param right
* @param target
* @return
*/
private static int partition(int[] nums, int left, int right, int target) {
int pivot = nums[target];
swap(nums, target, right);
int j = left;
for (int i = left; i <= right; i++) {
if (nums[i] < pivot) {
swap(nums, j, i);
j++;
}
}
swap(nums, j, right);
return j;
}
/**
* 交换
* @param nums
* @param a
* @param b
*/
public static void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
复杂度分析：
- 时间复杂度：平均情况O(N), 最坏情况O($N^2$).
- 空间复杂度：O(1).
- 写作不易，转载请注明出处，喜欢的小伙伴可以关注公众号查看更多喜欢的文章。
- 联系方式：4272231@163.com
- QQ:95472323
-
微信:ffj2000
