题目描述

[牛客网]

11. 旋转数组的最小数字

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

NOTE:给出的所有元素都大于 0,若数组大小为 0,请返回 0。

解法

见《⌨️ LeetCode 153. 寻找旋转排序数组中的最小值》(本博客)。

乍看之下跟 LeetCode 这道题完全一样,其实跟 LeetCode 相比,该题少了一个限制,即「数组内可能存在重复的数字」。多了这个条件之后,我们应该多考虑几种情况:

  1. 旋转数组的时候正好切在这个重复数字的中间,此时 left 的值等于 right 的值;
  2. left 的值可能等于 middle 的值。

对于第 1 种情况,其实我们可以不用考虑,因为实际上我们只需要比较 left 的值跟 middle 的值,来判断下一步应该往左半段还是右半段进行。所以只需要考虑第 2 种情况。举例来说,假如原数组是 [0, 1, 1, 1, 1],那么其旋转数组可能是 [1, 0, 1, 1, 1] 或者 [1, 1, 1, 0, 1],在这两种情况下我们往左往右走其实是无法判断的。更极端一点,如果该数组是一个非常长的数组,并且里面只含有一个 0,其余全是 1,那么假如给出其旋转数组,我们其实无法判断这个 0 在哪里。因此,如果遇到这种情况,我们可以比较开头跟结尾的数字,切掉其中一边即可。

代码略。