Java面試題沖刺第二十天--算法(1)
手?jǐn)]算法1:查找數(shù)組中重復(fù)元素和重復(fù)元素的個數(shù)
當(dāng)聽讓我寫這個算法時,紙筆還沒給到我手上,作為一個資深MySQL愛好者,瞬間從褲襠掏出一桿筆,打個哈欠的功夫,就在面試官臉上寫下了:
select num,count(num) from T group by num order by count(num) desc;
這個問題用的是數(shù)組,兩層循環(huán)比較或Map都可以解決,比較簡單,但是常問;方式如下:
1. 兩層循環(huán)比較方式
package com.softsec.demo; import java.util.HashMap; import java.util.Map; import java.util.Random; /** * 查找數(shù)組中重復(fù)元素和重復(fù)元素的個數(shù) * @author chenhh * */ public class getRepeat { /** * 循環(huán)比較處理 * @param arr */ public static void cyclingDemo ( int[] arr){ for (int x = 0; x < 10; x++) { int sumber1 = 0; for (int j = 0; j < 20; j++) { //數(shù)組中的數(shù)循環(huán)比較 if (x == arr[j]) { sumber1++; } else { continue; } } System.out.println(x + " -- 重復(fù)個數(shù):" + sumber1); } } public static void main (String[] args){ Random random = new Random(); int[] arr = new int[20]; for (int i = 0; i < 20; i++) { arr[i] = random.nextInt(10); if (i < arr.length - 1) { System.out.print(arr[i]+","); } else { System.out.print(arr[i] + "\r\n 結(jié)果:" + "\r\n" ); } } // 輸出arr數(shù)組中重復(fù)元素,重復(fù)數(shù)量 // 循環(huán)處理 cyclingDemo(arr); // map處理 // mapDemo(arr); }
打印結(jié)果:
0,3,4,0,6,5,8,1,3,1,9,3,6,3,7,5,7,1,1,1
結(jié)果:
0 -- 重復(fù)個數(shù):2
1 -- 重復(fù)個數(shù):5
2 -- 重復(fù)個數(shù):0
3 -- 重復(fù)個數(shù):4
4 -- 重復(fù)個數(shù):1
5 -- 重復(fù)個數(shù):2
6 -- 重復(fù)個數(shù):2
7 -- 重復(fù)個數(shù):2
8 -- 重復(fù)個數(shù):1
9 -- 重復(fù)個數(shù):1Process finished with exit code 0
2. 轉(zhuǎn)成Map集合處理方式
package com.softsec.demo; import java.util.HashMap; import java.util.Map; import java.util.Random; /** * 查找數(shù)組中重復(fù)元素和重復(fù)元素的個數(shù) * @author chenhh * */ public class getRepeat { /** * 轉(zhuǎn)成集合處理 * @param arr */ public static void mapDemo ( int[] arr){ //將數(shù)據(jù)轉(zhuǎn)成集合 Map<Integer, Integer> map = new HashMap(); for (int a = 0; a < arr.length; a++) { if (map.get(arr[a])!=null){ map.put(arr[a],map.get(arr[a])+1); } else { map.put(arr[a],1); } } for (int i = 0; i <10 ; i++) { System.out.println(i + " -- 重復(fù)個數(shù):" + map.get(i)); } } } public static void main (String[] args){ Random random = new Random(); int[] arr = new int[20]; for (int i = 0; i < 20; i++) { arr[i] = random.nextInt(10); if (i < arr.length - 1) { System.out.print(arr[i]+","); } else { System.out.print(arr[i] + "\r\n 結(jié)果:" + "\r\n" ); } } // 輸出arr數(shù)組中重復(fù)元素,重復(fù)數(shù)量 // 循環(huán)處理 // cyclingDemo(arr); // map處理 mapDemo(arr); } }
打印結(jié)果:
2,2,7,7,1,6,1,7,1,9,1,2,1,9,9,4,0,3,5,1
結(jié)果:
0 -- 重復(fù)個數(shù):1
1 -- 重復(fù)個數(shù):6
2 -- 重復(fù)個數(shù):3
3 -- 重復(fù)個數(shù):1
4 -- 重復(fù)個數(shù):1
5 -- 重復(fù)個數(shù):1
6 -- 重復(fù)個數(shù):1
7 -- 重復(fù)個數(shù):3
8 -- 重復(fù)個數(shù):null
9 -- 重復(fù)個數(shù):3Process finished with exit code 0
手?jǐn)]算法2:寫個二分查找demo吧
二分查找的條件是對一組有序數(shù)組的查找,所以要先確定查找的數(shù)組是否有序,在使用二分查找的時候先要對數(shù)組進(jìn)行排序。
加個排序多麻煩?所以面試官不指定無序數(shù)組時,就都當(dāng)有序的就行。無序你用什么二分法是吧?
二分算法步驟
1.首先確定整個查找區(qū)間的中間位置mid = ( left + right )/ 2
2.用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進(jìn)行比較;
★ 若相等,則查找成功
★ 若大于,則在后(右)半個區(qū)域繼續(xù)進(jìn)行折半查找
★ 若小于,則在前(左)半個區(qū)域繼續(xù)進(jìn)行折半查找
3.對確定的縮小區(qū)域再按折半公式,重復(fù)上述步驟,使用遞歸或普通while循環(huán)都可以。
這里我們對給定數(shù)列(有序){ 1, 20, 23, 24, 35, 46, 77, 78, 99, 100},通過二分法查找值為78的數(shù)據(jù)元素。
package com.softsec.demo; /** * 二分查找算法,兩種方法,一種遞歸一種非遞歸 * @author chenhh * */ public class BinaryQry { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr = new int[] { 1, 20, 23, 24, 35, 46, 77, 78, 99, 100 }; int index = search(arr,0,arr.length-1,78); //int index = search2(arr, 11); if (index == -1) { System.out.println("沒找到"); return; } System.out.println("在數(shù)組的第" + (index+1) + "位"); } /* * 遞歸方法查找 */ public static int search(int[] arr, int left, int right, int key) { if (left <= right) { int mid = (left + right) / 2; if (key < arr[mid]) { return search(arr, left, mid - 1, key); } else if (key > arr[mid]) { return search(arr, mid + 1, right, key); } else { return mid; } } return -1; } /* * 非遞歸方法查找 */ public static int search2(int[] arr, int key) { int left = 0; int right = arr.length - 1; int mid = 0; while (left <= right) { mid = (left + right) / 2; if (key == arr[mid]) { return mid; } else if (key > arr[mid]) { left = mid + 1; } else if (key < arr[mid]) { right = mid - 1; } } return -1; } }
手?jǐn)]算法3:把兩個有序數(shù)組合并成一個有序數(shù)組
對于兩個有序數(shù)組arrayM,arrayN,數(shù)組長度分別為m和n;
思路:
- 定義一個新數(shù)組newArray,長度為m+n;
- 定義兩個index(int),如:int start=0,end=0,用來記錄數(shù)組arrayM、arrayN的下標(biāo);
- 通過分別遍歷數(shù)組arrayM和arrayN的方式來比較每個值的大小,并將值存放到newArray中;
- 判斷start和end是否分別小于m和n,如果小于則繼續(xù)執(zhí)行,否則則表示有一個array遍歷結(jié)束,然后將另一個array剩余部分追加到newArray中即可;
package com.softsec.demo; /** * 兩個有序數(shù)組合并成一個有序數(shù)組的實現(xiàn)類 * @author chenhh * */ public class ArrayMerge { /** * 數(shù)組合并方法 * @param arrayM * @param arrayN * @return */ public static int[] mergeArray(int arrayM[],int arrayN[]){ int newArray[]; // 定義一個新數(shù)組,長度為兩個有序數(shù)組長度之和 newArray = new int[arrayM.length + arrayN.length]; // start:arrayM數(shù)組下標(biāo) end:arrayN數(shù)組下標(biāo) k:newArray新數(shù)組下標(biāo) int start=0,end=0,k=0; // 循環(huán)比較兩個數(shù)組,較小元素的放入新數(shù)組,較小元素所在數(shù)組下標(biāo)加一,較大元素對應(yīng)的數(shù)組下標(biāo)不加一,直到某一個下標(biāo)等于數(shù)組長度時退出循環(huán) while(start<arrayM.length && end<arrayN.length) { if(arrayM[start] <= arrayN[end]) { newArray[k++] = arrayM[start++]; }else{ newArray[k++] = arrayN[end++]; } } /* 后面兩個while循環(huán)是用來保證兩個數(shù)組比較完之后剩下的一個數(shù)組里的元素能順利都放入新數(shù)組 * 此時較短數(shù)組已經(jīng)全部放入新數(shù)組,較長數(shù)組還有部分剩余,最后將剩下的部分元素放入新數(shù)組,因為數(shù)組是有序,所以直接把剩下的順序加入即可*/ while(start < arrayM.length) { newArray[k++] = arrayM[start++]; } while(end < arrayN.length) { newArray[k++] = arrayN[end++]; } return newArray; } /** * 數(shù)組打印方法 * @param arr */ public static void print(int[] arr) { for(int i=0; i<arr.length;i++) { if (i < arr.length -1) { System.out.print(arr[i]+","); } else { System.out.print(arr[i]); } } } public static void main(String[] args) { int[] arrayM = {1,3,5,7,8,9,14,16,21}; int[] arrayN = {0,10,20,30,40,50}; print(mergeArray(arrayM,arrayN)); } }
結(jié)果打印:
0,1,3,5,7,8,9,10,14,16,20,21,30,40,50
Process finished with exit code 0
總結(jié)
本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
mybatis-plus QueryWrapper 添加limit方式
這篇文章主要介紹了mybatis-plus QueryWrapper 添加limit方式,具有很好的參考價值,希望對大家有所2022-01-01Tornadofx學(xué)習(xí)筆記之IconTextFx開源庫整合5000+個字體圖標(biāo)
這篇文章主要介紹了Tornadofx學(xué)習(xí)筆記之IconTextFx開源庫整合5000+個字體圖標(biāo)的相關(guān)知識,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-12-12springboot中@RestController注解實現(xiàn)
在JavaWeb開發(fā)中,Spring框架及其組件SpringMVC因高效和強大功能而廣受歡迎,@RestController注解是SpringMVC中的重要組成部分,下面就來介紹一下,感興趣的可以了解一下2024-09-09spring @Cacheable擴(kuò)展實現(xiàn)緩存自動過期時間及自動刷新功能
用過spring cache的朋友應(yīng)該會知道,Spring Cache默認(rèn)是不支持在@Cacheable上添加過期時間的,雖然可以通過配置緩存容器時統(tǒng)一指定,本文主要介紹了如何基于spring @Cacheable擴(kuò)展實現(xiàn)緩存自動過期時間以及緩存即將到期自動刷新,2024-02-02關(guān)于spring依賴注入的方式以及優(yōu)缺點
這篇文章主要介紹了關(guān)于spring依賴注入的方式以及優(yōu)缺點,依賴注入,是IOC的一個方面,是個通常的概念,它有多種解釋,這概念是說你不用創(chuàng)建對象,而只需要描述它如何被創(chuàng)建,需要的朋友可以參考下2023-07-07