04-旋转数组最小的数字
ALEX CODE PARK 2020-02-10
算法
数组
# 题目描述
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为 1。
# 思路分析
把数组从大到小排列,然后输出最小数字,这种思路的时间复杂度是 O(n)也没有利用旋转数组的一些特点,并不是题的意图,算是一种方法。 旋转之后的数组实际上可以划分为两个排序的子数组,而且前面的子数组的元素都大于或者等于后面的子数组的元素。最小的元素刚好是这两个子数组的分界线。在排序的数组中可以用二分查找实现 O(logn)的查找。
1.我们用两个指针 low 和 high 分别指向数组的第一个元素和最后一个元素。按照题目的旋转的规则,第一个元素应该是大于等于最后一个元素的;但是如果不是旋转,第一个元素肯定小于或等于最后一个元素。
2.找到数组的中间元素。中间元素大于最后一个元素,则中间元素位于前面的递增子数组,此时最小元素位于中间元素的后面。我们可以让第一个指针 low 指向中间元素。
3.中间元素小于最后一个元素,则中间元素位于后面的递增子数组,此时最小元素位于中间元素的前面。我们可以让第二个指针 high 指向中间元素。
4.中间元素等于最后一个元素,则将第二个指针向前移,然后继续比较。
# 代码实现
function pickMin(arr) {
let left = 0;
let right = arr.length - 1;
let mid;
while (left + 1 != right) {
mid = Math.floor((left + right) / 2);
if (arr[mid] <= arr[right]) {
right = mid;
} else {
left = mid;
}
}
return arr[right] > arr[left] ? arr[left] : arr[right];
// 不能使用 (arr[right]-arr[left]) 做判断
// 数字只有0 -0 会被转成false 其余为true
}
console.log(pickMin([4, 5, 1, 2, 3]));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18