侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

11 旋转数组的最小数字

Lin2J
2021-07-21 / 0 评论 / 1 点赞 / 109 阅读 / 1,265 字 / 正在检测是否收录...

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

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。  

方法一:二分查找

题目给的数组是有序数组,可以考虑使用二分查找,可以将遍历法的线性级别转化为对数级别

假定数组的左边位置是 $left$ ,右边是 $right$,$left$ 和 $right$ 的中心位置为 $mid,mid = (left + mid) / 2$。

  • 若 $nums[mid] < nums[right]$ , 说明 $[mid, right]$ 区间是递增的,那么最小值应该出现在 $[left, mid]$ 区间。

  • 若 $nums[mid] > nums[right]$, 说明 $[mid, right]$ 区间是先递增后递减的,那么最小值应该现在 $(mid + 1, right]$ 区间。$nums[mid]$ 不会是最小值。

  • 若 $nums[mid] == nums[right]$, 则无法判断 $[mid, right]$ 区间的单调性,但是可以把 $nums[right]$ 去掉。因为即使去掉 $nums[right]$ ,数组中还有 $nums[mid]$ ,所以不会对结果产生影响,把区间缩减为 $[left, right)$。

补充说明:

上面的思路中,一直都是 $mid$ 和 $right$ 的对比,那么能不能将 $left$ 和 $mid$ 对比呢?

举例:$[3, 4, 5, 1, 2]$ 与 $[1, 2, 3, 4, 5]$ ,此时,中间位置的值都比左边大,但最小值一个在后面,一个在前面,因此这种做法不能有效地减治。

代码:

public int minArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int l = 0;
    int r = nums.length - 1;
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if(nums[mid] < nums[r]){
            r = mid;
        } else if (nums[mid] > nums[r]){
            l = mid+1;
        } else {
            // 舍弃 nums[r]
            r--;
        }
    }
    return nums[r];
}

复杂度分析

  • 时间复杂度$O(logN)$: 在特例情况下(例如 $[1,1,1,1]$),会退化到 $O(N)$ 。

  • 空间复杂度$O(1)$:$l, r, mid$ 使用的都是常数大小的空间。

1

评论区