一道腾讯算法题，拿好不谢~
大家好，我是程序员吴师兄。
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题11.旋转数组的最小数字。根据统计，在腾讯的算法面试环节出现频率较高，属于简单中等难度。
题目链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
一、题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组[3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为 1。
示例 1：
输入：[3,4,5,1,2]
输出：1
示例 2：
输入：[2,2,2,0,1]
输出：0
二、题目解析
这道题最直观的解法是 从头到尾遍历数组一次，轻轻松松就能找出最小的元素。
这种思路的时间复杂度显然是 O(n)。
很显然，这种做法 没有利用输入的旋转数组的特性，所以在面试环节面试官肯定会问你：还能优化一下吗？。
一般的，O(n) 复杂度的优化我们都是往 二分查找 这个思路上去考虑的。
设置 start, end 指针分别指向 numbers 数组左右两端，取它们的中点 mid = (start + end ) / 2，然后将 numbers[mid] 与 numbers[end] 进行对比：
1、当 numbers[mid] > numbers[end]
此时，mid 在 左排序数组 中，而旋转点 x 一定在 [ mid + 1，end ] 闭区间内，所以接下来的操作是在 [ mid + 1，end ] 区间内寻找旋转点，相应的，改变 start 的值为 mid + 1。
2、numbers[mid] < numbers[end]
此时，mid 在 右排序数组 中，而旋转点 x 一定在 [ start，mid ] 闭区间内，所以接下来的操作是在 [ start，mid ] 区间内寻找旋转点，相应的，改变 end 的值为 mid 。
3、numbers[mid] = numbers[end]
三、动画描述
四、图片描述
五、参考代码
class Solution {
public int minArray(int[] numbers) {
//设置 start, end 指针分别指向 numbers 数组左右两端
int start = 0, end = numbers.length - 1;
//循环判断处理，直到找到结果
while (start < end) {
// mid 为中点（这里向下取整，比如 （ 2 + 7 ）/ 2 = 4 )
int mid = (start + end) / 2;
//当 mid 点所在元素大于数组末端的元素时，这意味着 [start , mid] 是有序的数组
if (numbers[mid] > numbers[end]){
// 所以旋转点在 [ mid + 1, end ] 区间里面 ，更新 start 的位置为 mid + 1
start = mid + 1;
}else if (numbers[mid] < numbers[end]){
// 当 mid 点所在元素小于数组开始端的元素时，这意味着 [mid , end] 是有序的数组
// 所以旋转点在 [ start, mid ] 区间里面 ，更新 end 的位置为 mid
end = mid;
//思考题?：为什么 start 是更新为 mid + 1，而 end 却是更新为 mid
}else{
//此时，出现了 numbers[mid] = numbers[end] 的情况，无法判断
// [ start , mid ] 为有序数组区间
// 还是 [ mid , end ] 为有序数组区间
// 比如： [1, 0, 1, 1, 1] 和 [1, 1, 1, 0, 1]
// 所以这里采取遍历的方式
return findMin(numbers,start,end);
}
}
return numbers[start];
}
public int findMin(int[] numbers,int start,int end){
int result = numbers[start];
for(int i = start;i <= end;i++){
if (numbers[i] < result) {
result = numbers[i];
}
}
return result;
}
}
六、复杂度分析
时间复杂度
时间复杂度为 O(log2N)。
空间复杂度
空间复杂度为 O(1)。
七、相关标签
- 二分查找
- 数组
腾讯云开发者
