JAVA中尋找最大的K個數(shù)解法
更新時間：2014年04月18日 09:49:05 作者：
尋找最大的K個數(shù)，這個是面試中比較常見的一道題，網(wǎng)上也有很多例子，在這里是比較傳統(tǒng)的解法
這個題拿到之后首先會想到排序，排好序之后在選取選取最大的K個數(shù)。排序選擇快速排序是個比較好的選擇。
好了，讓我們來進(jìn)行第一個解法：快速排序
代碼如下
復(fù)制代碼 代碼如下:
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
int key = arr[start];
int right = start;
int left = end;
while (right < left) {
while (right < left && arr[left] > key) {
left --;
}
if (right < left) {
arr[right] = arr[left];
}
while (right < left && arr[right] <= key) {
right ++;
}
if (right < left) {
arr[left] = arr[right];
}
}
arr[right] = key;
quickSort(arr, start, right-1);
quickSort(arr, left+1, end);
}
}
快速排序之后，數(shù)組會是有序的，上面的排序是從小到大的，所以我們輸出應(yīng)該是下面這樣
復(fù)制代碼 代碼如下:
int k = 4;
for (int i=arr.length-1; i>=arr.length-k; i--) {
System.out.println(arr[i]+" ");
}
for (int i=arr.length-1; i>=arr.length-k; i--) {
System.out.println(arr[i]+" ");
}
。第一個解法已經(jīng)好了，但是有沒有更好的辦法。
答案是有的！我們可以選擇部分排序，接下來我們使用選擇排序來做解決這個問題。
代碼如下：
復(fù)制代碼 代碼如下:
public static int[] selectSortK(int[] arr, int k) {
if(arr == null || arr.length == 0) {
return null;
}
int[] newArr = new int[k];
List<Integer> list = new ArrayList<Integer>();//記錄每次最大數(shù)的下標(biāo)
for (int i=0; i<k; i++) {
int maxValue = Integer.MIN_VALUE; //最大值
int maxIndex = i;
for (int j=0; j<arr.length; j++) {
if (arr[j] > maxValue && !list.contains(j) ) {
maxValue = arr[j];
maxIndex = j;
}
}
if (!list.contains(maxIndex)) {//如果不存在，就加入
list.add(maxIndex);
newArr[i] = maxValue;
}
}
return newArr;
}
if(arr == null || arr.length == 0) {
return null;
}
int[] newArr = new int[k];
List<Integer> list = new ArrayList<Integer>();//記錄每次最大數(shù)的下標(biāo)
for (int i=0; i<k; i++) {
int maxValue = Integer.MIN_VALUE; //最大值
int maxIndex = i;
for (int j=0; j<arr.length; j++) {
if (arr[j] > maxValue && !list.contains(j) ) {
maxValue = arr[j];
maxIndex = j;
}
}
if (!list.contains(maxIndex)) {//如果不存在，就加入
list.add(maxIndex);
newArr[i] = maxValue;
}
}
return newArr;
}
您可能感興趣的文章:
相關(guān)文章
下面小編就為大家?guī)硪黄猨ava使用sigar 遇到問題的快速解決方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-06-06
這是工作中遇到的問題,記錄下來,也方便自己后面查看操作步驟,也方便各位遇到這個問題,不至于卡太久,如有錯誤或未考慮完全的地方,望不吝賜教2023-11-11
詳解Java如何使用責(zé)任鏈默認(rèn)優(yōu)雅地進(jìn)行參數(shù)校驗(yàn)
項(xiàng)目中參數(shù)校驗(yàn)十分重要，它可以保護(hù)我們應(yīng)用程序的安全性和合法性。這篇文章主要介紹了如何使用責(zé)任鏈默認(rèn)優(yōu)雅地進(jìn)行參數(shù)校驗(yàn)，需要的可以參考一下2023-03-03
深入分析Android系統(tǒng)中SparseArray的源碼
這篇文章主要介紹了深入分析Android系統(tǒng)中SparseArray的源碼,SparseArray為Java實(shí)現(xiàn),需要的朋友可以參考下2015-07-07
@Transaction,@Async在同一個類中注解失效的原因分析及解決
這篇文章主要介紹了@Transaction,@Async在同一個類中注解失效的原因分析及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-12-12
Java類的序列化版本唯一標(biāo)識符serialVersionUID使用
serialVersionUID是一個類的序列化版本唯一標(biāo)識符,用于確保在反序列化過程中類的實(shí)例與序列化文件中的類版本相匹配,它在版本兼容性和安全性方面起著關(guān)鍵作用2025-01-01
SpringMVC運(yùn)行時出現(xiàn)404錯誤的解決辦法匯總(基本包含所有錯誤可能)
初學(xué)SpringMVC基本都會碰到404問題（確實(shí)也困擾了我好長時間）,但出現(xiàn)404問題的原因有很多,如果確認(rèn)路徑,代碼沒問題,并且服務(wù)器可以正常啟動,依然出現(xiàn)404問題的話,就根據(jù)本篇步驟逐一排查,需要的朋友可以參考下2024-04-04
Java如何實(shí)現(xiàn)http接口參數(shù)和返回值加密
這篇文章主要介紹了Java如何實(shí)現(xiàn)http接口參數(shù)和返回值加密問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章主要為大家介紹了restTemplate超時處理的策略方案，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-06-06
這篇文章主要介紹了Springboot整合thymleaf模板引擎過程解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-11-11