1. 利用快排的思想找數組中最大K元素，但是找到最大K元素 是排序后的數組 地址索引為K位置上的元素

但是利用快排的思想 不需要進行排序 只需要找到 地址索引=k 位置 前k-1個元素 不一定是排序的但是 前k-1個元素一定不小于(>=)索引k位置上的值 .

? ?快排思想：

?1.進行一次快排（將大的元素放在前半段，小的元素放在后半段）,?假設得到的中軸為p=partition()

2.判斷?k?-1==p?-?low，如果成立，直接輸出a[p]，（因為前半段有k?-?1個大于a[p]的元素，故a[p]為第 ? ? K大的元素）

3.如果?k?-1?<?p?-?low，?則第k大的元素在前半段，此時更新high?=?p?-?1，繼續進行步驟1

4.如果?k?-1?>?p?-?low，?則第k大的元素在后半段，此時更新low?=?p?+?1,?且?k?=?k?-(p?-?low?+1) ，繼續步驟1.?

快速排序中partition函數特性：調整函數 讓大于基點元素處在前半段，小于基點元素處在后半段.

package com.offerr;/**找 數組中 第K大的數字*/ public class Test_02 {public static void main(String[] args) {int [] array={10,10,10,10,20,30,30,40,40};//int index=Partition(array, 0, array.length-1);int k=4;System.out.print(getMaxK(array,0, array.length-1, k));}private static int count=1;// 大于index 點大的點數 index-low+1 private static int getMaxK(int [] array,int low ,int hign,int k){if(low> hign)return -1;int index=Partition(array, low, hign);count=index-low+1;// 比基點大 的 點個數if(count>k){return getMaxK(array, low, index-1, k); }else if( count < k ){ // 點在后半部分return getMaxK(array, index+1,hign,k-count);}else { return array[index];}}public static int Partition(int [] a,int low ,int high){/**快排核心算法 先移動末指針 在移動首指針 直到 i>j* 大*/int i=low,j=high,temp=a[low];if(low < high){while(i<j){while(i<j && temp>=a[j])j--;if(i<j)// 雙重驗證{a[i]=a[j];i++;}while(i<j && temp<=a[i])i++;if(i<j){a[j]=a[i];j--;}}a[i]=temp;}return i;} }

總結：這里無法處理 數組中重復的元素 如果數組 10 10 10 20 20 20 30 30，利用此算法得到第3大元素明顯輸出結果 20 。

如果我們想要第3大的元素 10 。對于這種方法?

解法一：直接進行快速排序，從快速排序之后的數組中遍歷數組剔除相同value的元素找到第3大的元素。

解法二：利用Set集合的特性 將數組用Set進行 處理在進行元素的排序。Java中利用集合框架TreeSet。

總結

以上是生活随笔為你收集整理的数组中最大第K元素(快排思想)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。