在算法面試中，面試官總是喜歡圍繞鏈表、排序、二叉樹、二分查找來做文章，而大多數(shù)人都可以跟著專業(yè)的書籍來做到倒背如流。而面試官并不希望招收的是一位記憶功底很好，但不會(huì)活學(xué)活用的程序員。所以學(xué)會(huì)數(shù)學(xué)建模和分析問題，并用合理的算法或數(shù)據(jù)結(jié)構(gòu)來解決問題相當(dāng)重要。
面試題：打印出旋轉(zhuǎn)數(shù)組的最小數(shù)字
題目：把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組 {3，4，5，1，2} 為數(shù)組 {1，2，3，4，5} 的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為 1。
要想實(shí)現(xiàn)這個(gè)需求很簡單，我們只需要遍歷一遍數(shù)組，找到最小的值后直接退出循環(huán)。代碼實(shí)現(xiàn)如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
public class test08 { public static int getthemin(int nums[]) { if (nums == null || nums.length == 0) { throw new runtimeexception("input error!"); } int result = nums[0]; for (int i = 0; i < nums.length - 1; i++) { if (nums[i + 1] < nums[i]) { result = nums[i + 1]; break; } } return result; } public static void main(string[] args) { // 典型輸入，單調(diào)升序的數(shù)組的一個(gè)旋轉(zhuǎn) int[] array1 = {3, 4, 5, 1, 2}; system.out.println(getthemin(array1)); // 有重復(fù)數(shù)字，并且重復(fù)的數(shù)字剛好的最小的數(shù)字 int[] array2 = {3, 4, 5, 1, 1, 2}; system.out.println(getthemin(array2)); // 有重復(fù)數(shù)字，但重復(fù)的數(shù)字不是第一個(gè)數(shù)字和最后一個(gè)數(shù)字 int[] array3 = {3, 4, 5, 1, 2, 2}; system.out.println(getthemin(array3)); // 有重復(fù)的數(shù)字，并且重復(fù)的數(shù)字剛好是第一個(gè)數(shù)字和最后一個(gè)數(shù)字 int[] array4 = {1, 0, 1, 1, 1}; system.out.println(getthemin(array4)); // 單調(diào)升序數(shù)組，旋轉(zhuǎn)0個(gè)元素，也就是單調(diào)升序數(shù)組本身 int[] array5 = {1, 2, 3, 4, 5}; system.out.println(getthemin(array5)); // 數(shù)組中只有一個(gè)數(shù)字 int[] array6 = {2}; system.out.println(getthemin(array6)); // 數(shù)組中數(shù)字都相同 int[] array7 = {1, 1, 1, 1, 1, 1, 1}; system.out.println(getthemin(array7)); }} |
打印結(jié)果沒什么毛病。不過這樣的方法顯然不是最優(yōu)的，我們看看有沒有辦法找出更加優(yōu)質(zhì)的方法處理。
有序，還要查找？
找到這兩個(gè)關(guān)鍵字，我們不免會(huì)想到我們的二分查找法，但不少小伙伴肯定會(huì)問，我們這個(gè)數(shù)組旋轉(zhuǎn)后已經(jīng)不是一個(gè)真正的有序數(shù)組了，不過倒像是兩個(gè)遞增的數(shù)組組合而成的，我們可以這樣思考。
我們可以設(shè)定兩個(gè)下標(biāo) low 和 high，并設(shè)定 mid = (low + high)/2，我們自然就可以找到數(shù)組中間的元素 array[mid]，如果中間的元素位于前面的遞增數(shù)組，那么它應(yīng)該大于或者等于 low 下標(biāo)對應(yīng)的元素，此時(shí)數(shù)組中最小的元素應(yīng)該位于該元素的后面，我們可以把 low 下標(biāo)指向該中間元素，這樣可以縮小查找的范圍。
同樣，如果中間元素位于后面的遞增子數(shù)組，那么它應(yīng)該小于或者等于 high 下標(biāo)對應(yīng)的元素。此時(shí)該數(shù)組中最小的元素應(yīng)該位于該中間元素的前面。我們就可以把 high 下標(biāo)更新到中位數(shù)的下標(biāo)，這樣也可以縮小查找的范圍，移動(dòng)之后的 high 下標(biāo)對應(yīng)的元素仍然在后面的遞增子數(shù)組中。
不管是更新 low 還是 high，我們的查找范圍都會(huì)縮小為原來的一半，接下來我們再用更新的下標(biāo)去重復(fù)新一輪的查找。直到最后兩個(gè)下標(biāo)相鄰，也就是我們的循環(huán)結(jié)束條件。
說了一堆，似乎已經(jīng)繞的云里霧里了，我們不妨就拿題干中的這個(gè)輸入來模擬驗(yàn)證一下我們的算法。
- input：{3，4，5，1，2}
- 此時(shí) low = 0，high = 4，mid = 2，對應(yīng)的值分別是：num[low] = 3，num[high] = 2，num[mid] = 5
- 由于 num[mid] > num[low]，所以 num[mid] 應(yīng)該是在左邊的遞增子數(shù)組中。
- 更新 low = mid = 2，num[low] = 5，mid = (low+high)/2 = 3，num[mid] = 1;
- high - low ≠ 1 ，繼續(xù)更新
- 由于 num[mid] < num[high]，所以斷定 num[mid] = 1 位于右邊的自增子數(shù)組中；
- 更新 high = mid = 3，由于 high - mid = 1,所以結(jié)束循環(huán)，得到最小值 num[high] = 1;
我們再來看看 java 中如何用代碼實(shí)現(xiàn)這個(gè)思路：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
public class test08 { public static int getthemin(int nums[]) { if (nums == null || nums.length == 0) { throw new runtimeexception("input error!"); } // 如果只有一個(gè)元素，直接返回 if (nums.length == 1) return nums[0]; int result = nums[0]; int low = 0, high = nums.length - 1; int mid; // 確保 low 下標(biāo)對應(yīng)的值在左邊的遞增子數(shù)組，high 對應(yīng)的值在右邊遞增子數(shù)組 while (nums[low] >= nums[high]) { // 確保循環(huán)結(jié)束條件 if (high - low == 1) { return nums[high]; } // 取中間位置 mid = (low + high) / 2; // 代表中間元素在左邊遞增子數(shù)組 if (nums[mid] >= nums[low]) { low = mid; } else { high = mid; } } return result; } public static void main(string[] args) { // 典型輸入，單調(diào)升序的數(shù)組的一個(gè)旋轉(zhuǎn) int[] array1 = {3, 4, 5, 1, 2}; system.out.println(getthemin(array1)); // 有重復(fù)數(shù)字，并且重復(fù)的數(shù)字剛好的最小的數(shù)字 int[] array2 = {3, 4, 5, 1, 1, 2}; system.out.println(getthemin(array2)); // 有重復(fù)數(shù)字，但重復(fù)的數(shù)字不是第一個(gè)數(shù)字和最后一個(gè)數(shù)字 int[] array3 = {3, 4, 5, 1, 2, 2}; system.out.println(getthemin(array3)); // 有重復(fù)的數(shù)字，并且重復(fù)的數(shù)字剛好是第一個(gè)數(shù)字和最后一個(gè)數(shù)字 int[] array4 = {1, 0, 1, 1, 1}; system.out.println(getthemin(array4)); // 單調(diào)升序數(shù)組，旋轉(zhuǎn)0個(gè)元素，也就是單調(diào)升序數(shù)組本身 int[] array5 = {1, 2, 3, 4, 5}; system.out.println(getthemin(array5)); // 數(shù)組中只有一個(gè)數(shù)字 int[] array6 = {2}; system.out.println(getthemin(array6)); // 數(shù)組中數(shù)字都相同 int[] array7 = {1, 1, 1, 1, 1, 1, 1}; system.out.println(getthemin(array7)); // 特殊的不知道如何移動(dòng) int[] array8 = {1, 0, 1, 1, 1}; system.out.println(getthemin(array8)); }} |
前面我們提到在旋轉(zhuǎn)數(shù)組中，由于是把遞增排序數(shù)組的前面的若干個(gè)數(shù)字搬到數(shù)組后面，因?yàn)榈谝粋€(gè)數(shù)字總是大于或者等于最后一個(gè)數(shù)字，而還有一種特殊情況是移動(dòng)了 0 個(gè)元素，即數(shù)組本身，也是它自己的旋轉(zhuǎn)數(shù)組。這種情況本身數(shù)組就是有序的了，所以我們只需要返回第一個(gè)元素就好了，這也是為什么我先給 result 賦值為 nums[0] 的原因。
上述代碼就完美了嗎？我們通過測試用例并沒有達(dá)到我們的要求，我們具體看看 array8 這個(gè)輸入。先模擬計(jì)算機(jī)運(yùn)行分析一下：
- low = 0, high = 4, mid = 2, nums[low] = 1, nums[high] = 1,nums[mid] = 1;
- 由于 nums[mid] >= nums[low]，故認(rèn)定 nums[mid] = 1 在左邊遞增子數(shù)組中；
- 所以更新 high = mid = 2,mid = (low+high)/2 = 1;
- nums[low] = 1,nums[mid] = 1,nums[high] = 1;
- high - low ≠ 1，繼續(xù)循環(huán)；
- 由于 nums[mid] >= nums[low]，故認(rèn)定 nums[mid] = 1 在左邊遞增子數(shù)組中；
- 所以更新 high = mid = 1,由于 high - low = 1,故退出循環(huán)，得到 result = 1；
但我們一眼了然，明顯我們的最小值不是 1 ，而是 0 ，所以當(dāng) array[low]、array[mid]、array[high] 相等的時(shí)候，我們的程序并不知道應(yīng)該如何移動(dòng)，按照目前的移動(dòng)方式就默認(rèn) array[mid] 在左邊遞增子數(shù)組了，這顯然是不負(fù)責(zé)任的做法。
我們修正一下代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
public class test08 { public static int getthemin(int nums[]) { if (nums == null || nums.length == 0) { throw new runtimeexception("input error!"); } // 如果只有一個(gè)元素，直接返回 if (nums.length == 1) return nums[0]; int result = nums[0]; int low = 0, high = nums.length - 1; int mid = low; // 確保 low 下標(biāo)對應(yīng)的值在左邊的遞增子數(shù)組，high 對應(yīng)的值在右邊遞增子數(shù)組 while (nums[low] >= nums[high]) { // 確保循環(huán)結(jié)束條件 if (high - low == 1) { return nums[high]; } // 取中間位置 mid = (low + high) / 2; // 三值相等的特殊情況，則需要從頭到尾查找最小的值 if (nums[mid] == nums[low] && nums[mid] == nums[high]) { return midinorder(nums, low, high); } // 代表中間元素在左邊遞增子數(shù)組 if (nums[mid] >= nums[low]) { low = mid; } else { high = mid; } } return result; } /** * 查找數(shù)組中的最小值 * * @param nums 數(shù)組 * @param start 數(shù)組開始位置 * @param end 數(shù)組結(jié)束位置 * @return 找到的最小的數(shù)字 */ public static int midinorder(int[] nums, int start, int end) { int result = nums[start]; for (int i = start + 1; i <= end; i++) { if (result > nums[i]) result = nums[i]; } return result; } public static void main(string[] args) { // 典型輸入，單調(diào)升序的數(shù)組的一個(gè)旋轉(zhuǎn) int[] array1 = {3, 4, 5, 1, 2}; system.out.println(getthemin(array1)); // 有重復(fù)數(shù)字，并且重復(fù)的數(shù)字剛好的最小的數(shù)字 int[] array2 = {3, 4, 5, 1, 1, 2}; system.out.println(getthemin(array2)); // 有重復(fù)數(shù)字，但重復(fù)的數(shù)字不是第一個(gè)數(shù)字和最后一個(gè)數(shù)字 int[] array3 = {3, 4, 5, 1, 2, 2}; system.out.println(getthemin(array3)); // 有重復(fù)的數(shù)字，并且重復(fù)的數(shù)字剛好是第一個(gè)數(shù)字和最后一個(gè)數(shù)字 int[] array4 = {1, 0, 1, 1, 1}; system.out.println(getthemin(array4)); // 單調(diào)升序數(shù)組，旋轉(zhuǎn)0個(gè)元素，也就是單調(diào)升序數(shù)組本身 int[] array5 = {1, 2, 3, 4, 5}; system.out.println(getthemin(array5)); // 數(shù)組中只有一個(gè)數(shù)字 int[] array6 = {2}; system.out.println(getthemin(array6)); // 數(shù)組中數(shù)字都相同 int[] array7 = {1, 1, 1, 1, 1, 1, 1}; system.out.println(getthemin(array7)); // 特殊的不知道如何移動(dòng) int[] array8 = {1, 0, 1, 1, 1}; system.out.println(getthemin(array8)); }} |
我們再用完善的測試用例放進(jìn)去，測試通過。
總結(jié)
本題其實(shí)考察的點(diǎn)挺多的，實(shí)際上就是考察對二分查找的靈活運(yùn)用，不少小伙伴死記硬背二分查找必須遵從有序，而沒有學(xué)會(huì)這個(gè)二分查找的思想，這樣會(huì)導(dǎo)致只能想到循環(huán)查找最小值了。
不少小伙伴在面試中表態(tài)，android 原生態(tài)基本都封裝了常用算法，對面試這些無作用的算法表示抗議，其實(shí)這是相當(dāng)愚蠢的。我們不求死記硬背算法的實(shí)現(xiàn)，但求學(xué)習(xí)到其中巧妙的思想。只有不斷地提升自己的思維能力，才能助自己收獲更好的職業(yè)發(fā)展。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://www.jianshu.com/p/06f6fd4b9d4d
