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

作者: linzeliang

题目

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

思路1(暴力遍历)

  • 不用题目给的部分有序的条件,直接从头开始遍历找最小值

    代码

class Solution {
    public int minArray(int[] numbers) {
        int min = numbers[0];
        for (int i : numbers) {
            if (i < min) {
                min = i;
            }
        }
        return min;
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\)
  • 空间复杂度:\(O(1)\)

思路2

  • 使用二分法

  • 不用(left + right) / 2,而用left + (right - left) / 2是为了防止如果leftright相加超过int范围导致溢出

  • 先选取三个点将数组一分为二。由于该数组是将有序数组旋转得到的,所以如果最左边的小于最右边的,那么就一定是有序的;如果左边的小于中间的,说明最小值是在右半部分里,然后从右半部分继续二分查找就可以了,反之就从左边部分二分查找

  • 如果左边中间和右边的这三个都相等,那么们无法判断了,只能从左边开始遍历查找了

    代码

实现一:

class Solution {
    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length-1;
        int mid = left;

        while (numbers[left] >= numbers[right]) {
            if (right - left == 1) {
                mid = right;
                break;
            }

            mid = (left + right) / 2;

            // 遇到无法判断的情况,只能遍历了
            if (numbers[left] == numbers[right] && numbers[left] == numbers[mid]) {
                int min = left;
                for (int i = left+1; i < right; i++) {
                    if (numbers[min] > numbers[i]) {
                        min = i;
                    }
                }
                mid = min;
                break;
            }

            if (numbers[left] <= numbers[mid]) {
                // 最小值在右半部分
                left = mid;
            } else if (numbers[mid] <= numbers[right]) {
                // 最小值在左边部分
                right = mid;
            }
        }

        return numbers[mid];
    }
}

实现二:

class Solution {
    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (numbers[mid] < numbers[right]) {
                right = mid;
            } else if (numbers[mid] > numbers[right]) {
                left = mid + 1;
                right--;
            }
        }

        return numbers[left];
    }
}

复杂度分析

  • 时间复杂度:\(O(logN)\)
  • 空间复杂度:\(O(1)\)

    原文创作:linzeliang

    原文链接:https://www.cnblogs.com/linzeliang1222/p/15418103.html

更多推荐

更多
这里什么都没有

近期文章

更多
文章目录

    推荐作者

    更多