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