數(shù)組中的第K個(gè)最大元素
問題描述
給定整數(shù)數(shù)組 nums 和整數(shù) k，請返回?cái)?shù)組中第 k 個(gè)最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素。詳見leetcode215
問題分析
之前我們已經(jīng)使用堆排序/堆查找的方式解決了這個(gè)問題。詳見堆在查找和排序中的應(yīng)用找到數(shù)組中的第K個(gè)最大元素，最直接的方式就是使用快速排序使數(shù)組有序，之后返回?cái)?shù)組的第K個(gè)元素，當(dāng)然可以使用快速排序來實(shí)現(xiàn)了，其實(shí)只要是需要數(shù)組有序，都可以通過快排來實(shí)現(xiàn)，因?yàn)榭焖倥判蛳鄬Ω咝?。比如找最值，二分查找也需要?shù)組有序等。
代碼實(shí)現(xiàn)
可以使用快速排序的原理和實(shí)現(xiàn)中任一方式實(shí)現(xiàn)快速排序
public int findKthLargest(int[] nums, int k) {
quickSort(nums,0,nums.length-1);
return nums[k-1];
}
public void quickSort(int[] nums,int left,int right){
if(left>=right){
return;
}
int pivot = nums[right];
int i = left-1;
for(int j=left;j<right;j++){
if(nums[j]>pivot){
i++;
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
int pivotIndex = i+1;
int temp = nums[right];
nums[right] = nums[pivotIndex];
nums[pivotIndex] = temp;
quickSort(nums,left,pivotIndex-1);
quickSort(nums,pivotIndex+1,right);
}
注意：題目中要求設(shè)計(jì)時(shí)間復(fù)雜度為O(n)的算法，所以有一個(gè)測試樣例不通過。
文章來源地址http://www.zghlxwxcb.cn/news/detail-698912.html
快速排序的時(shí)間復(fù)雜度詳見快速排序的原理和實(shí)現(xiàn)
文章來源：http://www.zghlxwxcb.cn/news/detail-698912.html
到了這里，關(guān)于算法通關(guān)村-----快速排序的應(yīng)用的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
