排序-二分查找

例题:

  • 寻找旋转排序数组中的最小值
    网址:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
    前沿: 下面给出两种解法,分别从两个角度:
  • 常规想法,考虑的性质是:序列中最小的数据要么是第一个要么是第一个左边数据大于右边的位置
  • 二分查找的方式

方法1:

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        if(n==1) return nums[0];
        int tmp = nums[0];
        auto iter = nums.begin();
        nums.insert(iter, *iter-1);    //增加一个开头数
        iter = nums.begin()+1;
        for(;iter!=nums.end();iter++){
            if(*prev(iter,1)>*iter){
                tmp = *iter;
                break;
            }
        }
        return tmp;
    }
};

注意点:采用容器的prev函数获取前一个的地址,所以用迭代器的时候需要考虑增加一个无用的开头新数。

方法2:

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        if(n==1) return nums[0];
        int low = 0;
        int high = n-1;
        while(low<high){
            int mid = low + (high - low)/2;
            if(nums[mid]<nums[high])
                high = mid;
            else 
                low = mid+1;
        }
        return nums[low];
    }
};

注意点:这里面二分注意点就是中间元素和最后一个元素的判断关系,如果中间元素小于最后元素,那么mid右边去掉;否则左边去掉。

上一篇:你真知道如何高效用mapPartitions吗?


下一篇:java中HashMap有什么用,举例说明?