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