剑指 Offer 11. 旋转数组的最小数字

剑指 Offer 11. 旋转数组的最小数字

思路:

  1. 初始化 :初始化start和end分别指向nums数组的左右两端
  2. 循环二分:令mid = (start + end) / 2(start <= mid < end),分以下三种情况:
    (1)当nums[mid] >nums[j]时,则选转点在左排序数组中,即在[mid + 1, j]中,此时令i = mid + 1;
    (2)当nums[mid] < nums[j]时,则旋转点在[i, mid]中,则令j = mid;
    (3)当nums[mid] = nums[j]时,无法判断,解决:令j = j - 1;
  3. 返回值:当i = j 时跳出二分循环,并返回旋转点的值nums[i]即可。
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int i = 0, j = numbers.size() - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
};
上一篇:UVA10202 POJ2466 ZOJ1895 Pairsumonious Numbers【算术计算】


下一篇:剑指Offer11.旋转数组的最小数字