給一個(gè)無序的包涵n個(gè)元素的數(shù)組与斤，找出其中第k大的數(shù)（n > k）。
初看到這個(gè)題的時(shí)候荚恶，作為一個(gè)寫了一段時(shí)間java的人撩穿，立刻能想到的一種解法就是：
class Solution {
public int kthLargestElement(int k, int[] nums) {
Arrays.sort(nums);
return nums[nums.length - k];
}
};
時(shí)間復(fù)雜度時(shí)NlgN, 空間復(fù)雜度時(shí)O(1).
看起來貌似不錯(cuò)，但既然這道題目被廣泛地討論谒撼，就肯定還有其他解法食寡，比如說：
class Solution {
public int kthLargestElement(int k, int[] nums) {
// write your code here
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int val : nums) {
pq.add(val);
if(pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
};
當(dāng)然建堆需要額外的空間，而且時(shí)間復(fù)雜度上并沒有多少提升廓潜，所以不能算什么優(yōu)化抵皱。
更好的一種解法是利用快速排序的劃分思想，這種解法是一種O(n)的解法
class Solution {
public int kthLargestElement(int k, int[] nums) {
//打亂數(shù)組避免最壞情況
shuffle(nums);
k = nums.length - k;
int lo = 0, hi = nums.length - 1;
while(lo < hi){
int j = partition(nums, lo, hi);
if(j < k){
lo = j + 1;
}else if(j > k){
hi = j - 1;
}else{
break;
}
}
return nums[k];
}
private int partition(int[] nums, int lo, int hi){
int i = lo;
int j = hi + 1;
while(true){
while(i < hi && nums[++i] < nums[lo]);
while(j > lo && nums[lo] < nums[--j]);
if(j <= i) break;
exch(nums, i, j);
}
exch(nums, lo, j);
return j;
}
private void exch(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void shuffle(int a[]) {
Random random = new Random();
for(int ind = 1; ind < a.length; ind++) {
int r = random.nextInt(ind + 1);
exch(a, ind, r);
}
}
};
