AcWing 22. 旋转数组的最小数字（C++）- 有价值+二分

柔情只为你懂 2022-09-14 09:47 83阅读 0赞

题目链接：[https://www.acwing.com/problem/content/description/20/][https_www.acwing.com_problem_content_description_20]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
思路：  
当出现如下的包含重复元素的vector时，需要先去重，然后再使用二分。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
解法一：

class Solution {
        
    public:
        int findMin(vector<int>& nums) {
        
            if(nums.size()==0) return -1;
            
            int l=0,r=nums.size()-1;
            while(l<r&&nums[r]==nums[0]) r--;//如果头和尾元素相同时，去重
            
            if(nums[l]<=nums[r]) return nums[0];//本身是有序的，或者所有数据值都相同
            while(l<r){
        
                int mid=l+r>>1;
                
                if(nums[mid]<nums[0]) r=mid;
                else l=mid+1;
            }
            
            return nums[r];
        }
    };

解法二：

class Solution {
        
    public:
        int findMin(vector<int>& nums) {
        
            if(nums.size()==0) return -1;
            //二分法，升序排序，且可以明显的两分
            int low=0,high=nums.size()-1,mid;
    
            while(low<high){
        
                mid=(low+high)>>1;
    
                if(nums[high]<nums[mid]) low=mid+1;
                else if(nums[high]>nums[mid]) high=mid;
                else if(nums[high]==nums[mid]) high--;//防止存在相同元素的干扰
            }
    
            return nums[low];
        }
    };

[https_www.acwing.com_problem_content_description_20]: https://www.acwing.com/problem/content/description/20/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f371017247174dfdaee8facc845b4c38.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/fc91e29fc80d42adb1ccf14e71f780ce.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/88e8d0430a804af4855c6ece54da404a.png