(LeetCode 153)Find Minimum in Rotated Sorted Array
LeetCode in Array Find sorted minimum rotated
2023-09-14 08:59:06 时间
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7
might become 4 5 6 7 0 1 2
).
Find the minimum element.
You may assume no duplicate exists in the array.
题目:
给定一旋转有序数组,求该数组的最小值。
思路:
- 二分查找Binary Search
- 比较简单,不详述,主要在于二分查找过程的循环不变量的判断
- 递归思想
- 旋转有序数组的循环不变量:
- 旋转数组的最后一个值一定小于第一个值(无旋转情况例外)。在二分循环时,对于区间的判断很重要。
- 以最右值为pivot,当num[mid]>num[right],为了维持旋转不变量,即数组的第一个值大于最后一个值,应当将left=mid,这样依旧num[left]>num[right]。当num[mid]<num[right],应当将right=mid,这样对于无旋转的数组同样适用,因为num[mid]肯定小于num[right],数组不断地往左收缩,最终会到num[0]。
- 以最左值为pivot,同样可以通过二分求旋转数组的最小值,但对于无旋转数组而言,num[mid]肯定大于num[left],数组会不断地往右收缩,最终会到num[len-1].
- 所以,要么采用最右值来收缩二分查找区间,要么将无旋转数组单独考虑。
- 最小值小于左右两边的值,满足其一即可。
- if(nums[mid]<nums[mid-1]) return nums[mid];
- if(nums[mid]>nums[mid+1]) return nums[mid+1];
- 因为数组是从0下标开始的,因此最好通过第二种情况来判断。
- 方法总结:
- 单独考虑无旋转数组,即一开始就判断num[0]<num[len-1]?如果是,则返回num[0]。再考虑旋转数组,通过最左值或者最右值来收缩二分查找的区间。对于最小值的判断,采用if(nums[mid]>nums[mid+1]) return nums[mid+1];如果出现无旋转数组,单独考虑无旋转数组的话,时间效率更高。
- 不单独考虑无旋转数组,则通过最右值来收缩二分查找的区间。对于最小值的判断,采用if(nums[mid]>nums[mid+1]) return nums[mid+1];
代码:
1、非递归
class Solution { public: int findMin(vector<int>& nums) { int len=nums.size(); int left=0; int right=len-1; int mid; // if(nums[left]<nums[right]) // return nums[left]; while(left<=right){ if(left==right) return nums[left]; mid=(left+right)/2; // if(nums[mid]<nums[mid-1]) // return nums[mid]; if(nums[mid]>nums[mid+1]) return nums[mid+1]; if(nums[mid]>nums[right]) left=mid; if(nums[mid]<nums[right]) right=mid; } } };
2、递归
class Solution { public: int findMin(vector<int> &num) { int left = 0, right = num.size() - 1; return BinarySearch(num, left, right); } private: int BinarySearch(vector<int> &num, int left, int right) { if(left==right) return num[left]; int mid = (left + right) / 2; // if(num[mid] < num[mid - 1]) return num[mid]; if(num[mid] > num[mid + 1]) return num[mid + 1]; if(num[mid] < num[right]) return BinarySearch(num, left, mid); if(num[mid] > num[right]) return BinarySearch(num, mid, right); } };
相关文章
- ☆打卡算法☆LeetCode 205. 同构字符串 算法解析
- 逆波兰表达式求值(leetcode 150)
- 知乎搬运:刷LeetCode经常心态崩,是我智商不够吗?
- leetcode-11盛最多水的容器「建议收藏」
- LeetCode 867. 转置矩阵
- JavaScript刷LeetCode模板技巧篇(一)
- JavaScript刷LeetCode拿offer-滑动窗口
- leetcode刷题(123)——63. 不同路径 II
- 每日一道leetcode:6. N 字形变换
- MySQL OR和IN:比较和选择(mysqlor和in)
- 进行字符串比较使用Oracle IN运算符比较字符串(oracle使用in)
- 查询Oracle中执行多列IN查询的技巧(oracle多列in)
- MySQL中的IN运算符技巧(mysql查in)
- MySQL排序:IN排列法(mysql按照in排序)
- 深入Linux内核:IN后缀操作系统之旅(linux系统in后缀)
- 深入探究Mysql中IN与AND逻辑运算的应用(mysql中in与and)
- 利用Oracle中的If In语句减少数据处理时间(oracle中if in)