在算法面试中，面试官总是喜欢围绕链表、排序、二叉树、二分查找来做文章，而大多数人都可以跟着专业的书籍来做到倒背如流。而面试官并不希望招收的是一位记忆功底很好，但不会活学活用的程序员。所以学会数学建模和分析问题，并用合理的算法或数据结构来解决问题相当重要。
面试题：打印出旋转数组的最小数字
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组 {3，4，5，1，2} 为数组 {1，2，3，4，5} 的一个旋转，该数组的最小值为 1。
要想实现这个需求很简单，我们只需要遍历一遍数组，找到最小的值后直接退出循环。代码实现如下：
|
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) { // 典型输入，单调升序的数组的一个旋转 int[] array1 = {3, 4, 5, 1, 2}; system.out.println(getthemin(array1)); // 有重复数字，并且重复的数字刚好的最小的数字 int[] array2 = {3, 4, 5, 1, 1, 2}; system.out.println(getthemin(array2)); // 有重复数字，但重复的数字不是第一个数字和最后一个数字 int[] array3 = {3, 4, 5, 1, 2, 2}; system.out.println(getthemin(array3)); // 有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字 int[] array4 = {1, 0, 1, 1, 1}; system.out.println(getthemin(array4)); // 单调升序数组，旋转0个元素，也就是单调升序数组本身 int[] array5 = {1, 2, 3, 4, 5}; system.out.println(getthemin(array5)); // 数组中只有一个数字 int[] array6 = {2}; system.out.println(getthemin(array6)); // 数组中数字都相同 int[] array7 = {1, 1, 1, 1, 1, 1, 1}; system.out.println(getthemin(array7)); }} |
打印结果没什么毛病。不过这样的方法显然不是最优的，我们看看有没有办法找出更加优质的方法处理。
有序，还要查找？
找到这两个关键字，我们不免会想到我们的二分查找法，但不少小伙伴肯定会问，我们这个数组旋转后已经不是一个真正的有序数组了，不过倒像是两个递增的数组组合而成的，我们可以这样思考。
我们可以设定两个下标 low 和 high，并设定 mid = (low + high)/2，我们自然就可以找到数组中间的元素 array[mid]，如果中间的元素位于前面的递增数组，那么它应该大于或者等于 low 下标对应的元素，此时数组中最小的元素应该位于该元素的后面，我们可以把 low 下标指向该中间元素，这样可以缩小查找的范围。
同样，如果中间元素位于后面的递增子数组，那么它应该小于或者等于 high 下标对应的元素。此时该数组中最小的元素应该位于该中间元素的前面。我们就可以把 high 下标更新到中位数的下标，这样也可以缩小查找的范围，移动之后的 high 下标对应的元素仍然在后面的递增子数组中。
不管是更新 low 还是 high，我们的查找范围都会缩小为原来的一半，接下来我们再用更新的下标去重复新一轮的查找。直到最后两个下标相邻，也就是我们的循环结束条件。
说了一堆，似乎已经绕的云里雾里了，我们不妨就拿题干中的这个输入来模拟验证一下我们的算法。
- input：{3，4，5，1，2}
- 此时 low = 0，high = 4，mid = 2，对应的值分别是：num[low] = 3，num[high] = 2，num[mid] = 5
- 由于 num[mid] > num[low]，所以 num[mid] 应该是在左边的递增子数组中。
- 更新 low = mid = 2，num[low] = 5，mid = (low+high)/2 = 3，num[mid] = 1;
- high - low ≠ 1 ，继续更新
- 由于 num[mid] < num[high]，所以断定 num[mid] = 1 位于右边的自增子数组中；
- 更新 high = mid = 3，由于 high - mid = 1,所以结束循环，得到最小值 num[high] = 1;
我们再来看看 java 中如何用代码实现这个思路：
|
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!"); } // 如果只有一个元素，直接返回 if (nums.length == 1) return nums[0]; int result = nums[0]; int low = 0, high = nums.length - 1; int mid; // 确保 low 下标对应的值在左边的递增子数组，high 对应的值在右边递增子数组 while (nums[low] >= nums[high]) { // 确保循环结束条件 if (high - low == 1) { return nums[high]; } // 取中间位置 mid = (low + high) / 2; // 代表中间元素在左边递增子数组 if (nums[mid] >= nums[low]) { low = mid; } else { high = mid; } } return result; } public static void main(string[] args) { // 典型输入，单调升序的数组的一个旋转 int[] array1 = {3, 4, 5, 1, 2}; system.out.println(getthemin(array1)); // 有重复数字，并且重复的数字刚好的最小的数字 int[] array2 = {3, 4, 5, 1, 1, 2}; system.out.println(getthemin(array2)); // 有重复数字，但重复的数字不是第一个数字和最后一个数字 int[] array3 = {3, 4, 5, 1, 2, 2}; system.out.println(getthemin(array3)); // 有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字 int[] array4 = {1, 0, 1, 1, 1}; system.out.println(getthemin(array4)); // 单调升序数组，旋转0个元素，也就是单调升序数组本身 int[] array5 = {1, 2, 3, 4, 5}; system.out.println(getthemin(array5)); // 数组中只有一个数字 int[] array6 = {2}; system.out.println(getthemin(array6)); // 数组中数字都相同 int[] array7 = {1, 1, 1, 1, 1, 1, 1}; system.out.println(getthemin(array7)); // 特殊的不知道如何移动 int[] array8 = {1, 0, 1, 1, 1}; system.out.println(getthemin(array8)); }} |
前面我们提到在旋转数组中，由于是把递增排序数组的前面的若干个数字搬到数组后面，因为第一个数字总是大于或者等于最后一个数字，而还有一种特殊情况是移动了 0 个元素，即数组本身，也是它自己的旋转数组。这种情况本身数组就是有序的了，所以我们只需要返回第一个元素就好了，这也是为什么我先给 result 赋值为 nums[0] 的原因。
上述代码就完美了吗？我们通过测试用例并没有达到我们的要求，我们具体看看 array8 这个输入。先模拟计算机运行分析一下：
- low = 0, high = 4, mid = 2, nums[low] = 1, nums[high] = 1,nums[mid] = 1;
- 由于 nums[mid] >= nums[low]，故认定 nums[mid] = 1 在左边递增子数组中；
- 所以更新 high = mid = 2,mid = (low+high)/2 = 1;
- nums[low] = 1,nums[mid] = 1,nums[high] = 1;
- high - low ≠ 1，继续循环；
- 由于 nums[mid] >= nums[low]，故认定 nums[mid] = 1 在左边递增子数组中；
- 所以更新 high = mid = 1,由于 high - low = 1,故退出循环，得到 result = 1；
但我们一眼了然，明显我们的最小值不是 1 ，而是 0 ，所以当 array[low]、array[mid]、array[high] 相等的时候，我们的程序并不知道应该如何移动，按照目前的移动方式就默认 array[mid] 在左边递增子数组了，这显然是不负责任的做法。
我们修正一下代码：
|
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!"); } // 如果只有一个元素，直接返回 if (nums.length == 1) return nums[0]; int result = nums[0]; int low = 0, high = nums.length - 1; int mid = low; // 确保 low 下标对应的值在左边的递增子数组，high 对应的值在右边递增子数组 while (nums[low] >= nums[high]) { // 确保循环结束条件 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); } // 代表中间元素在左边递增子数组 if (nums[mid] >= nums[low]) { low = mid; } else { high = mid; } } return result; } /** * 查找数组中的最小值 * * @param nums 数组 * @param start 数组开始位置 * @param end 数组结束位置 * @return 找到的最小的数字 */ 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) { // 典型输入，单调升序的数组的一个旋转 int[] array1 = {3, 4, 5, 1, 2}; system.out.println(getthemin(array1)); // 有重复数字，并且重复的数字刚好的最小的数字 int[] array2 = {3, 4, 5, 1, 1, 2}; system.out.println(getthemin(array2)); // 有重复数字，但重复的数字不是第一个数字和最后一个数字 int[] array3 = {3, 4, 5, 1, 2, 2}; system.out.println(getthemin(array3)); // 有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字 int[] array4 = {1, 0, 1, 1, 1}; system.out.println(getthemin(array4)); // 单调升序数组，旋转0个元素，也就是单调升序数组本身 int[] array5 = {1, 2, 3, 4, 5}; system.out.println(getthemin(array5)); // 数组中只有一个数字 int[] array6 = {2}; system.out.println(getthemin(array6)); // 数组中数字都相同 int[] array7 = {1, 1, 1, 1, 1, 1, 1}; system.out.println(getthemin(array7)); // 特殊的不知道如何移动 int[] array8 = {1, 0, 1, 1, 1}; system.out.println(getthemin(array8)); }} |
我们再用完善的测试用例放进去，测试通过。
总结
本题其实考察的点挺多的，实际上就是考察对二分查找的灵活运用，不少小伙伴死记硬背二分查找必须遵从有序，而没有学会这个二分查找的思想，这样会导致只能想到循环查找最小值了。
不少小伙伴在面试中表态，android 原生态基本都封装了常用算法，对面试这些无作用的算法表示抗议，其实这是相当愚蠢的。我们不求死记硬背算法的实现，但求学习到其中巧妙的思想。只有不断地提升自己的思维能力，才能助自己收获更好的职业发展。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://www.jianshu.com/p/06f6fd4b9d4d
