1:思路分析
在未排序的数组中找到第 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 ≤ 数组的长度。
2:具体实现
对数组进行快速排序
private static int partation(int[] number, int left, int right) {
if (number == null || number.length <= 0) {
return 0;
}
int mid = number[left];------------------//基准数
while (left < right) {
while (left < right && number[right] > mid) {//从右边开始将小于基准数的放在左边
right--;
}
number[left] = number[right];
while (left < right && number[left] < mid) {//从左边开始将大于基准数的放在右边
left++;
}
number[right] = number[left];
}
number[left] = mid;-----------------//排序完成之后中间的那个元素
return left;
}
上面完成之后数组就是一个有序数组了
private static int findKthLargest(int[] number, int k) {
if (number == null || number.length <= 0 || k > number.length) {
return 0;
}
int left =0;
int right = number.length -1;
while (left < right) {
int pos = partation(number, left, right);-----//有序数组中间元素的index
if (pos == k -1) {--------------//找到直接跳出循环
break;
} else if (pos < k -1) {--------------//如果小于k-1，那么向数组右边继续查找
left = pos + 1;
} else {-//如果大于k-1，那么向数组左边继续查找
right = pos -1;
}
}
return number[k-1];
}
