Java面試題沖刺第二十三天–算法(2)
面試題1：你說一下常用的排序算法都有哪些？
追問1：談一談你對快排的理解吧
快速排序，顧名思義就是一種以效率快為特色的排序算法，快速排序（Quicksort）是對冒泡排序的一種改進。由英國計算機專傢:托尼·霍爾（Tony Hoare）在1960年提出。
從排序數組中找出一個數，可以隨機取，也可以取固定位置，一般是取第一個或最後一個，稱為基準數。然後將比基準小的排在左邊，比基準大的放到右邊；
如何放置呢，就是和基準數進行交換，交換完左邊都是比基準小的，右邊都是比較基準大的，這樣就將一個數組分成瞭兩個子數組，然後再按照同樣的方法把子數組再分成更小的子數組，直到不能分解（子數組隻有一個值）為止。以此達到整個數據變成有序序列。
快速排序采用瞭一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)，現在各種語言中自帶的排序庫很多使用的都是快速排序。
空間復雜度
快速排序是一種原地排序，隻需要一個很小的棧作為輔助空間，空間復雜度為O(log2n)，所以適合在數據集比較大的時候使用。
時間復雜度
時間復雜度比較復雜，最好的情況是O(n)，最差的情況是O(n2)，所以平時說的O(nlogn)，為其平均時間復雜度。
- O(n)：理想的情況，每次劃分所選擇的中間數恰好將當前序列幾乎等分，經過log2n趟劃分，便可得到長度為1的子表。這樣，整個算法的時間復雜度為O(nlog2n)。
- O(n2)：最壞的情況，每次所選的中間數是當前序列中的最大或最小元素，這使得每次劃分所得的子表中一個為空表，另一子表的長度為原表的長度-1。這樣，長度為n的數據表的快速排序需要經過n趟劃分，使得整個排序算法的時間復雜度為O(n2)。
追問2：說一下快排的算法原理
算法步驟
- 選定一個基準數（一般取第一位數字）作為中心點（Pivot）；
- 將大於Pivot的數字放到Pivot的左邊；
- 將小於Pivot的數字放到Pivot的右邊；
- 第一次排序結束後，分別對左右子序列繼續遞歸重復前三步操作，直到左右子序列長度隻有單個元素為止。
demo示例
實例數組：arr[] = {19，97，9，17，1，8}；
取出基準數Pivot，以該值為中心軸。
快速排序中的規則：右邊有坑，就從左邊Arr[L + n]取值來填，反之左邊有坑，則從右邊Arr[R – n]取值來填；
從左邊取的基準值，左邊的Arr[L]就空出來瞭，則先從右側取值來填，從最右側下標開始，在Arr[R] 取到第一個值“8”；
將取到的Arr[R]與基準值比較，發現小於基準值，則插入到Arr[R]，占到瞭基準值Pivot的位置上。
然後從Arr[L+1]的位置取出值，繼續向右匹配並排序，將匹配到的值（匹配規則如下）插入到右側Arr[R]的空位置上；
匹配規則：大於基準值的插入到Arr[R]，如果小於，則直接忽略並跳過，繼續向右取值，直到坐標L和坐標R重合。
發現取出的值大於Pivot（基準值），則將其插入到Arr[R]。
左邊有坑，從右邊Arr[R-1]繼續匹配，Arr[R-1] = 1，小於基準值，則插入到Arr[L]的坑中；
右邊有坑瞭，繼續從左邊取值繼續匹配，則取到Arr[L+1] = 9,小於基準值，則忽略並跳過，繼續找Arr[L + 1]繼續匹配。
繼續從左邊坐標 + 1 取值繼續匹配，則取到Arr[L] = 17，又小於基準值，則忽略並跳過，繼續找Arr[L + 1]繼續匹配。
最後L坐標和R坐標重合瞭，將Pivot基準值填入
至此，快速排序第一輪完整流程結束，分出瞭左右子序列，左邊都是小於Pivot基準值的，右邊都是大於Pivot基準值的。
繼續對左、右子序列遞歸進行處理，一直縮小到左、右都是一個值，則快速排序結束，最終得出順序數組{1,8,9,17,19,97}；中間遞歸流程這裡不再贅述。
追問3：來吧！給我手敲一個快排
package com.softsec.demo;
/**
* Created with IDEA
*
* @Author Chensj
* @Date 2020/5/17 19:04
* @Description
* @Version 1.0
*/
public class quickSortDemo {
public static void main(String[] args) {
// 創建測試數組
int[] arr = new int[]{19,97,9,17,1,8};
System.out.println("排序前：");
showArray(arr); // 打印數組
// 調用快排接口
quickSort(arr);
System.out.println("\n" + "排序後：");
showArray(arr);// 打印數組
}
/**
* 快速排序
* @param array
*/
public static void quickSort(int[] array) {
int len;
if(array == null
|| (len = array.length) == 0
|| len == 1) {
return ;
}
sort(array, 0, len - 1);
}
/**
* 快排核心算法，遞歸實現
* @param array
* @param left
* @param right
*/
public static void sort(int[] array, int left, int right) {
if(left > right) {
return;
}
// base中存放基準數
int base = array[left];
int i = left, j = right;
while(i != j) {
// 順序很重要，先從右邊開始往左找，直到找到比base值小的數
while(array[j] >= base && i < j) {
j--;
}
// 再從左往右邊找，直到找到比base值大的數
while(array[i] <= base && i < j) {
i++;
}
// 上面的循環結束表示找到瞭位置或者(i>=j)瞭，交換兩個數在數組中的位置
if(i < j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
// 將基準數放到中間的位置（基準數歸位）
array[left] = array[i];
array[i] = base;
// 遞歸，繼續向基準的左右兩邊執行和上面同樣的操作
// i的索引處為上面已確定好的基準值的位置，無需再處理
sort(array, left, i - 1);
sort(array, i + 1, right);
}
/**
* 數組打印
* @param num
*/
private static void showArray(int[] num) {
for (int i = 0; i < num.length; i++) {
System.out.print(num[i] + " ");
}
}
}
面試題2：來！再給我手擼一個Spring
我：？？？
追問1：哦，咳咳…說一下構成遞歸的前提條件有啥？
函數內部調用的自身函數的編程技巧稱為遞歸（recursion）。
構成遞歸的條件：
- 子問題須與原始問題為同樣的事，且更為簡單；
- 不能無限制地調用本身，須有個出口，化簡為非遞歸狀況處理。
追問2：遞歸都有哪些優缺點？
優點：
1.簡潔
2.在樹的前序，中序，後序遍歷算法中，遞歸的實現明顯要比循環簡單得多。
缺點：
1.遞歸由於是函數調用自身，而函數調用是有時間和空間的消耗的：每一次函數調用，都需要在內存棧中分配空間以保存參數、返回地址以及臨時變量，而往棧中壓入數據和彈出數據都需要時間。（效率）
2.遞歸中很多計算都是重復的，由於其本質是把一個問題分解成兩個或者多個小問題，多個小問題存在相互重疊的部分，則存在重復計算，如fibonacci斐波那契數列的遞歸實現。（效率）
3.調用棧可能會溢出，其實每一次函數調用會在內存棧中分配空間，而每個進程的棧的容量是有限的，當調用的層次太多時，就會超出棧的容量，從而導致棧溢出。（性能）
追問3：給我手寫一個簡單的遞歸算法的實現吧
例如遞歸計算一下n的階乘
package com.softsec;
/**
* 遞歸計算n的階乘
* @author Chenhh
*/
public class demo {
public static void main(String[] args) {
System.out.println(recursion(5));
}
/**
* 遞歸計算n的階乘
*/
private static int recursion(int n) {
if (n <1) {
throw new IllegalArgumentException("參數必須大於0");
} else if (n == 1) {
return 1;
} else {
return n * recursion(n - 1);
}
}
}
面試題3： 10億個數中找出最大的100000個數（top K問題）
先拿100000個數建堆，然後一次添加剩餘元素，如果大於堆頂的數（100000中最小的），將這個數替換堆頂，並調整結構使之仍然是一個最小堆，這樣，遍歷完後，堆中的100000個數就是所需的最大的100000個。建堆時間復雜度是O(m)，算法的時間復雜度為1次建堆時間+n次堆調整時間=O(m+nlogm)=O(nlogm)（n為10億，m為100000）。
優化的方法：可以把所有10億個數據分組存放，比如分別放在1000個文件中。這樣處理就可以分別在每個文件的10^6個數據中找出最大的100000個數，合並到一起在再找出最終的結果。
top K問題
在大規模數據處理中，經常會遇到的一類問題：在海量數據中找出出現頻率最好的前k個數，或者從海量數據中找出最大的前k個數，這類問題通常被稱為top K問題。例如，在搜索引擎中，統計搜索最熱門的10個查詢詞；在歌曲庫中統計下載最高的前10首歌等。
針對top K類問題，通常比較好的方案是分治+Trie樹/hash+小頂堆（就是上面提到的最小堆），即先將數據集按照Hash方法分解成多個小數據集，然後使用Trie樹活著Hash統計每個小數據集中的query詞頻，之後用小頂堆求出每個數據集中出現頻率最高的前K個數，最後在所有top K中求出最終的top K。
對於有10億個整數，如何找出其中最大的10萬個這個問題
最容易想到的方法是將數據全部排序，然後在排序後的集合中進行查找，最快的排序算法的時間復雜度一般為O（nlogn），如快速排序。但是如果按每個int類型占4個字節，10億個整數就要占用4G的存儲空間，對於一些java運行內存小於4G的計算機而言，直接OOM（out of memory）瞭。其實即使內存能夠滿足要求（我機器內存都是8GB），該方法也並不高效，因為題目的目的是尋找出最大的100000個數即可，而排序卻是將所有的元素都排序瞭，做瞭很多的無用功。
第二種方法為局部淘汰法，該方法與排序方法類似，用一個容器保存前100000個數，然後將剩餘的所有數字——與容器內的最小數字相比，如果所有後續的元素都比容器內的100000個數還小，那麼容器內這個100000個數就是最大100000個數。如果某一後續元素比容器內最小數字大，則刪掉容器內最小元素，並將該元素插入容器，最後遍歷完這1億個數，得到的結果容器中保存的數即為最終結果瞭。此時的時間復雜度為O（n+m^2），其中m為容器的大小，即100000。
第三種方法是分治法，將10億個數據分成1000份，每份100萬個數據，找到每份數據中最大的100000個，最後在剩下的1000 * 100000個數據裡面找出最大的100000個。如果100萬數據選擇足夠理想，那麼可以過濾掉1億數據裡面99%的數據。100萬個數據裡面查找最大的100000個數據的方法如下：用快速排序的方法，將數據分為2堆，如果大的那堆個數N大於100000個，繼續對大堆快速排序一次分成2堆，如果大的那堆個數N大於100000個，繼續對大堆快速排序一次分成2堆，如果大堆個數N小於100000個，就在小的那堆裡面快速排序一次，找第100000-n大的數字；遞歸以上過程，就可以找到第10w大的數。參考上面的找出第10w大的數字，就可以類似的方法找到前100000大數字瞭。此種方法需要每次的內存空間為10^6*4=4MB，一共需要101次這樣的比較。
第四種方法是Hash法。如果這1億個書裡面有很多重復的數，先通過Hash法，把這10億個數字去重復，這樣如果重復率很高的話，會減少很大的內存用量，從而縮小運算空間，然後通過分治法或最小堆法查找最大的100000個數。
第五種方法采用最小堆。首先讀入前100000個數來創建大小為100000的最小堆，建堆的時間復雜度為O(m)（m為數組的大小即為100000），然後遍歷後續的數字，並於堆頂（最小）數字進行比較。如果比最小的數小，則繼續讀取後續數字；如果比堆頂數字大，則替換堆頂元素並重新調整堆為最小堆。整個過程直至10億個數全部遍歷完為止。然後按照中序遍歷的方式輸出當前堆中的所有100000個數字。該算法的時間復雜度為O（nmlogm），空間復雜度是100000（常數）。
總結
本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！
推薦閱讀：
- 詳解Java雙軸快速排序算法
- Java數據結構與算法入門實例詳解
- Java數據結構常見幾大排序梳理
- Java使用Arrays.sort()方法實現給對象排序
- Java 數據結構與算法系列精講之排序算法