1:思路分析
在未排序的數(shù)組中找到第 k 個最大的元素莉擒。請注意澜躺，你需要找的是數(shù)組排序后的第 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
說明:
你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長度稠氮。
2:具體實現(xiàn)
對數(shù)組進(jìn)行快速排序
private static int partation(int[] number, int left, int right) {
if (number == null || number.length <= 0) {
return 0;
}
int mid = number[left];------------------//基準(zhǔn)數(shù)
while (left < right) {
while (left < right && number[right] > mid) {//從右邊開始將小于基準(zhǔn)數(shù)的放在左邊
right--;
}
number[left] = number[right];
while (left < right && number[left] < mid) {//從左邊開始將大于基準(zhǔn)數(shù)的放在右邊
left++;
}
number[right] = number[left];
}
number[left] = mid;-----------------//排序完成之后中間的那個元素
return left;
}
上面完成之后數(shù)組就是一個有序數(shù)組了
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);-----//有序數(shù)組中間元素的index
if (pos == k -1) {--------------//找到直接跳出循環(huán)
break;
} else if (pos < k -1) {--------------//如果小于k-1曹阔，那么向數(shù)組右邊繼續(xù)查找
left = pos + 1;
} else {-//如果大于k-1，那么向數(shù)組左邊繼續(xù)查找
right = pos -1;
}
}
return number[k-1];
}
