JAVA中尋找最大的K個數(shù)解法
更新時間：2014年04月18日 09:49:05 作者：
尋找最大的K個數(shù)，這個是面試中比較常見的一道題，網(wǎng)上也有很多例子，在這里是比較傳統(tǒng)的解法
這個題拿到之后首先會想到排序，排好序之后在選取選取最大的K個數(shù)。排序選擇快速排序是個比較好的選擇。
好了，讓我們來進行第一個解法：快速排序
代碼如下
復(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ù)的下標
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ù)的下標
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)文章
本篇文章主要介紹了Spring 中如何控制2個bean中的初始化順序，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-10-10
這篇文章主要介紹了Java線程間通信不同步問題,結(jié)合實例形式分析了java線程間通信不同步問題的原理并模擬實現(xiàn)了線程間通信不同步情況下的異常輸出,需要的朋友可以參考下2019-10-10
Java?數(shù)據(jù)結(jié)構(gòu)與算法系列精講之貪心算法
我們可能在好多地方都會聽到貪心算法這一概念，并且它的算法思想也比較簡單就是說算法只保證局部最優(yōu)，進而達到全局最優(yōu)。但我們實際編程的過程中用的并不是很多，究其原因可能是貪心算法使用的條件比較苛刻，所要解決的問題必須滿足貪心選擇性質(zhì)2022-02-02
spring cloud gateway中如何讀取請求參數(shù)
這篇文章主要介紹了spring cloud gateway中如何讀取請求參數(shù)的操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
這篇文章主要介紹了基于Feign使用okhttp的填坑之旅，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-02-02
詳解OpenFeign服務(wù)調(diào)用(微服務(wù))
OpenFeign是Spring Cloud在Feign的基礎(chǔ)上支持了SpringMVC的注解，如@RequesMapping等等，這篇文章主要介紹了OpenFeign服務(wù)調(diào)用的相關(guān)知識,需要的朋友可以參考下2022-07-07
本文主要講解了java中對象基礎(chǔ)Object類，文中運用大量代碼講解的非常詳細，想學(xué)習(xí)相關(guān)知識的小伙伴可以參考一下這篇文章2021-09-09
springboot Interceptor攔截器excludePathPatterns忽略失效
這篇文章主要介紹了springboot Interceptor攔截器excludePathPatterns忽略失效的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
利用ScriptEngineManager實現(xiàn)字符串公式靈活計算的方法
今天小編就為大家分享一篇利用ScriptEngineManager實現(xiàn)字符串公式靈活計算的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
這篇文章主要給大家介紹了關(guān)于MyBatis查詢、新增、更新與刪除操作的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學(xué)習(xí)或者使用MyBatis具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2020-06-06