前言今天继续算法题：旋转数组中的最小数。输入一个按升序排列的数组的旋转，输出旋转后数组的最小元素。例如数组[3,4,5,1,2]是[1,2,3,4,5]的旋转，最小值为1。例1：输入：[3,4,5,1,2]输出：1例子2：输入：[2,2,2,0,1]输出：0解法1首先找到问题的根源：递增排序数组（可以重复），旋转，最小的element为递增数组，移动一部分到数组末尾，如：[1,2,3,4,5]//旋转后[3,4,5,1,2]中找到最小的数他们。那么我们最容易想到的第一个方案就是遍历数组，然后找到一个比前面的数小的数，那么这个数就是我们要找的最小数。因为通常后面的数都大于前面的数，所以如果小于前面的数，那么就是这个旋转数组的分界点，就是最小数。classSolution{publicintminArray(int[]numbers){for(inti=0;inumbers[i+1]){returnnumbers[i+1];}}returnnumbers[0];}}方法消费以后就不写这个了。由于每个测试用例不同，结果也相差太大，没有参考意义。时间复杂度遍历数组一次，所以时间复杂度为O(n)，空间复杂度不使用额外空间，所以空间复杂度为O(1)解二分法。可能有人会疑惑，二分法不是用来找时序数组的吗？轮换后算不算？再回顾一下二分法的要点：取任意一个关键数，判断即可。哪个区间是（键号前后）的值。那么在我们的旋转数组中，是否可以这样做呢？比如我们取中间值a和最后一个值b，如果a大于b，说明边界值在a和b之间，a之前的数据排序正确。如果a小于b，说明cutoff值在a之前，a和b之间的数据排序正确。比如刚才的[3,4,5,1,2]中，中间值5大于最后一个值2，说明截断值在5和2之间，也就是1。classSolution{publicintminArray(int[]numbers){intleft=0;intright=numbers.length-1;//二分查找条件while(leftnumbers[right]){left=mid+1;}else{right--;}}returnnumbers[left];}}之所以right=mid,left=mid+1是因为当numbers[mid]和numbers[mid]>numbers[right]时，mid不可能是最小的，所以设置为mid+1.时间复杂度二分法的最坏情况：n/(2的x次方)=1，x=long2n。所以时间复杂度是O(longn)，还有一种情况是所有元素都一样。这种情况下每次都执行right-1，所以时间复杂度为O(n)，空间复杂度没有使用额外的空间。所以空间复杂度为O(1)参考https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/submissions/本文转载自微信公众号「码上积木」，可通过以下二维码关注。转载本文请联系积木上的代码公众号。
