正文
题目描述#
在未排序的数组中找到第 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 ≤ 数组的长度。
我的代码#
class Solution { public int findKthLargest(int[] nums, int k) { int steps = nums.length / k + 1; int[] max = new int[k]; for (int i = 0; i < k; i++) { max[i]=Integer.MIN_VALUE; } for (int i = 0; i < steps; i++) { selectMaxfromArray(nums, i * k, (i + 1) * k, max); } int min = max[0]; for (int i = 1; i < max.length; i++) { if (min > max[i]) { min = max[i]; } } return min; } private void selectMaxfromArray(int[] nums, int start, int end, int[] max) { int[] newArray = new int[2 * max.length]; for (int i = 0; i < newArray.length; i++) { newArray[i]=Integer.MIN_VALUE; } for (int i = start, j = 0; i < end && i < nums.length; i++, j++) { newArray[j] = nums[i]; } for (int i = 0; i < max.length; i++) { newArray[i + max.length] = max[i]; } for (int i = 0; i < newArray.length; i++) { for (int j = i + 1; j < newArray.length; j++) { if (newArray[i] < newArray[j]) { int temp = newArray[i]; newArray[i] = newArray[j]; newArray[j] = temp; } } } for (int i = 0; i < max.length; i++) { max[i] = newArray[i]; } } }
结论#
* 虽然是自己写出来的，但是不尽人意 * 应当用堆来进行实现。。。明天复习一下堆的操作
