1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 11 题] “旋转数组的最小数字”做题记录

[剑指 Offer 第 2 版第 11 题] “旋转数组的最小数字”做题记录

第 11 题:旋转数组中的最小数字

传送门:AcWing:旋转数组的最小数字牛客网 online judge 地址

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。

输入一个升序的数组的一个旋转,输出旋转数组的最小元素。

例如数组 [3,4,5,1,2][1,2,3,4,5] 的一个旋转,该数组的最小值为 1

数组可能包含重复项。

注意:数组内所含元素非负,若数组大小为0,请返回-1。

样例:

输入:nums=[2, 2, 2, 0, 1]

输出:0

思路1 :这是典型的可以使用二分法解决的问题,应用二分法的模板。特别注意,数组可能包含重复项,因此中间项如果等于末尾项,例如:[1, 1, 1, 1, 1, 0, 1] ,不能砍掉一半,只能把末尾项排除掉。

Python 代码:

  class Solution:
        def findMin(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            size = len(nums)
            if size == 0:
                return -1
            l = 0
            r = size - 1
            while l < r:
                mid = l + (r - l) // 2

                if nums[mid] < nums[r]:
                    # mid 有可能是最小值
                    # [7,8,1,2,3]
                    r = mid
                elif nums[mid] > nums[r]:
                    # mid 肯定不是最小值
                    # [7,8,9,10,11,1,2,3]
                    l = mid + 1
                else:
                    # 都有可能,所以就把 r 排除了
                    # [1,1,1,1,1,0,1]
                    assert nums[mid] == nums[r]
                    r = r - 1
            return nums[l]

思路2 :还可以使用“分治法”,“分治法”就不用在乎有没有重复项了。但是“分治法”无异于把整个数组都看一遍,时间复杂度为 O(n)

Python 代码:

  class Solution:
        def findMin(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            size = len(nums)
            if size == 0:
                return -1
            if size == 1:
                return nums[0]
            return self.__findMin(nums, 0, size - 1)

        def __findMin(self, nums, left, right):
            if left == right:
                return nums[left]
            if left + 1 == right:
                return min(nums[left], nums[right])
            mid = left + (right - left) // 2
            return min(self.__findMin(nums, left, mid), self.__findMin(nums, mid + 1, right))

分析:可以使用二分查找的思想,因为最小的数字很可能出现在首位,从后向前扫描是求解这道题的重要技巧,否则需要分类讨论,就变得麻烦了(即让后面的指针向前移动)。

Java 代码:

  public class Solution {

        // 虽然可以通过,但是 O(n) 的复杂度并不理想
        public int minNumberInRotateArray(int[] array) {
            // {3,4,5,1,2}
            // 1 2 3 4 5
            int len = array.length;
            for (int i = 1; i < len - 1; i++) {
                if (array[i] < array[i - 1]) {
                    return array[i];
                }
            }
            // 如果走到这里,说明数组是升序的,直接返回第 0 号索引的元素就可以了
            return array[0];
        }

        public static void main(String[] args) {
            // int[] nums = new int[]{3, 4, 5, 1, 2};
            int[] nums = new int[]{1, 2, 3, 4, 5};
            Solution solution = new Solution();
            int minNumberInRotateArray = solution.minNumberInRotateArray(nums);
            System.out.println(minNumberInRotateArray);
        }
    }

Java 代码:

  public class Solution2 {

        public int minNumberInRotateArray(int[] array) {
            int len = array.length;
            if (len == 0) {
                return 0;
            }
            int first = 0;
            int last = len - 1;
            while (first < last) {
                int mid = first + (last - first) / 2;
                if (array[mid] > array[last]) {
                    first = mid + 1;
                } else if (array[mid] == array[last]) {
                    last = last - 1;
                } else {
                    last = mid;
                }
            }
            return array[first];
        }

        public static void main(String[] args) {
            // int[] nums = new int[]{3};
            // int[] nums = new int[]{3, 4, 5, 6, 7, 8, 9, 1, 2};
            // int[] nums = new int[]{1, 2, 3, 4, 5};
            int[] nums = new int[]{2, 2, 2, 1, 2};
            Solution2 solution2 = new Solution2();
            int minNumberInRotateArray = solution2.minNumberInRotateArray(nums);
            System.out.println(minNumberInRotateArray);
        }
    }

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 11 题] “旋转数组的最小数字”做题记录

链接:https://www.javajike.com/article/3262.html

« [剑指 Offer 第 2 版第 10 题] “跳台阶”做题记录
[剑指 Offer 第 2 版第 12 题] “矩阵中的路径”做题记录»

相关推荐

QR code