培训网站有哪些,网站建设费进项税金可以抵扣吗,网站下载免费新版,关于百度网站的优缺点难度#xff1a; 困难通过率#xff1a; 38.7%题目链接#xff1a;. - 力扣#xff08;LeetCode#xff09;
题目描述 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如#xff0c;数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的…难度 困难通过率 38.7%题目链接. - 力扣LeetCode
题目描述 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例 1
输入: [1,3,5]
输出: 1
示例 2
输入: [2,2,2,0,1]
输出: 0
说明
这道题是 寻找旋转排序数组中的最小值 的延伸题目。允许重复会影响算法的时间复杂度吗会如何影响为什么
解法
首先举两个例子下图中左边两幅是非递减数组绘制的图像右边是旋转后绘制的图像。可以看出旋转后右侧一定是小于等于左侧的。原数组中最小的值其实就是右半边的左端点。 既然是排序后的数组虽然经过了旋转但是直觉还是告诉我要使用二分查找。二分查找涉及到三个量 lo, hi,mid。我们的目标是找到右边部分的左端点。
如果 mid 落在左半边那么 lomid1否则设置 himid。这样不断缩小范围最终就能找到这个最低点。
那么如何确定 mid 落在那边呢由于左半边一定大于等于右半边因此可以使用 nums[mid] 和左半段左端点比较如果落在左半段那么 nums[mid] nums[0]。但是落在右半段也有可能 nums[mid] nums[0] 啊因为右侧的右端点可能和左侧左端点的值相同。(上图中第二种情况)
因此我们需要保证左半部分一定大于右半部分为此我们只需要做如下操作
while(nums[lo] nums[hi]){lo ;
}处理完成后我们在 [lo,hi] 上寻找最小值。若 nums[mid] nums[lo] 那么 mid 落在左半部分否则落在右侧。
经过一些朋友的提醒下我发现还存在其他一些特殊情况 特殊情况一如果数组中所有元素的值都相同那么 lo 就会一直增加最终越界。
特殊情况二如果左右两边相等的元素数量相那么循环完毕后 lo 就是右半边的左端点。前面提到的二分查找策略此时就失效了。
class Solution {
public:int minNumberInRotateArray(vectorint nums) {int lo 0, hi nums.size();while(lo hi nums[lo] nums.back()){lo ;}// 特殊情况一所有元素都相等if(lo hi){return nums[0];}// 特殊情况二if(nums[lo] nums.back()){return nums[lo];}int left_min nums[lo];while(lo hi){int mid lo (hi - lo) / 2;if(nums[mid] left_min){lo mid 1;}else{hi mid;}}return nums[lo];}
};
