【剑指offer系列题解】
【题目地址】
题目描述方法一:顺序查找 O(n)把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个升序的数组的一个旋转,输出旋转数组的最小元素。
例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转,该数组的最小值为 1 。
数组可能包含重复项。
注意:数组内所含元素非负,若数组大小为 0 ,请返回 −1 。
数据范围数组长度 [0,90]。
样例输入:nums = [2, 2, 2, 0, 1] 输出:0
最直接的方法就是从头往后遍历,直到前一个大于当前遍历的数字为止,当前遍历的这个元素就是最小值。
class Solution { public: int findMin(vector方法二:二分 O(n)& nums) { int n = nums.size(); if (n == 0) return -1; int i; for (i = 1; i < n; i++) if (nums[i - 1] > nums[i]) return nums[i]; return nums[0]; } };
下图中水平的图线代表元素相同,具体算法步骤如下:
- 如果该数组首尾元素有相同的,就先去除相同的元素,保证二分算法可以正常运行。因为我们不确定数组旋转过后首尾元素是否会出现相同的情况,为了不影响二分查找的进行,要进行去重操作,下图就是一个例子。
- 进行二分查找,找到一个临界点比 nums[0] 的元素刚好要小。
class Solution { public: int findMin(vector& nums) { int n = nums.size() - 1; if (n < 0) return -1; while (n > 0 && nums[n] == nums[0]) n--; //去掉数组最后与数组开头相同的部分 if (nums[0] <= nums[n]) return nums[0]; //如果此时数组已经有序,返回第一个元素 int l = 0, r = n; while (l < r) //一直二分,直到找到临界点 { int mid = l + r >> 1; if (nums[mid] < nums[0]) r = mid; else l = mid + 1; } return nums[r]; } };
欢迎大家在评论区交流~