题目已知一个长度为n的数组预先按照升序排列经由1到n次旋转后得到输入数组。例如原数组nums [0,1,2,4,5,6,7]在变化后可能得到若旋转4次则可以得到[4,5,6,7,0,1,2]若旋转7次则可以得到[0,1,2,4,5,6,7]注意数组[a[0], a[1], a[2], ..., a[n-1]]旋转一次的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值互不相同的数组nums它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。你必须设计一个时间复杂度为O(log n)的算法解决此问题。示例 1输入nums [3,4,5,1,2]输出1解释原数组为 [1,2,3,4,5] 旋转 3 次得到输入数组。示例 2输入nums [4,5,6,7,0,1,2]输出0解释原数组为 [0,1,2,4,5,6,7] 旋转 4 次得到输入数组。示例 3输入nums [11,13,15,17]输出11解释原数组为 [11,13,15,17] 旋转 4 次得到输入数组。提示n nums.length1 n 5000-5000 nums[i] 5000nums中的所有整数互不相同nums原来是一个升序排序的数组并进行了1至n次旋转大概思路我想的是这道题一般情景下就是会遇到两种情况一是该数组本身就没有被旋转就是一个递增的情况这种情况下最小值就是第一个数组元素第二种应该是大多数情况发生了一定量的旋转而最小值就在数组中间比如4、5、6、7、1、2、3这样的。分析一下这种情况这种情况下一定是最小数的左边有一个递增序列其右边有一个递增序列并且左边序列的每一个值都比右边最大的数还大因此我们可以以右边序列最大的数为基准去和二分产生的中间数进行对比最右边的数记作m当nums[mid]m时说明mid所处位置在左边的递增序列最小数在mid的右边此时更新leftmid1。反过来如果nums[mid]m时mid处在右边的递增序列上(右边递增序列的每一个数小于m),那么最小数在mid左边所以更新rightmid-1,这样让left和right逐渐靠近包裹住我们要找的最小数最终二分终止后得到的就是最小数。其实大致的思路是容易确定的主要是我们最终条件终止时得到的究竟是最小数么是left还是right呢还有就是有几种特殊情况我刚才分析的是第二种情况下的结果对于第一种情况这个算法成立么还有就是假如最右边恰好是最小数比如4、5、6、7、1这种情况算法正确吗。我是怎么确定二分的返回值和判断条件的怎么确定返回值是left还是right或者其他最终到底是left是答案还是right我是通过所有情况分析再给出结论的首先对于一般的数组比如....4、5、6、7、1、2、3....那么在用二分时基于我们的判断条件可以想象这个数组左右两边的省略号出现的数可能不一样可是mid无非出现在7的左侧和2的右侧或7和2的某个数或者1上面吧。假如mid直接一开始就指向了1那么1m所以rightmid-1指向7此时left和right中间都是比m大的数了left会不断靠近right而right定在7上了直到left变成7判断mid指向77m所以left指向1,二分结束left指向1此时left指向最小值。假如mid没直接指向1而是先指向了7或2比如7那么left会更新指向1此时right不断向左靠近直到mid又变成了指向1。最后结果和上面一样的left最终指向最小值。那么假如mid指向了2right会更新为1此时left会不断向右靠近直到left指向7mid指向7然后更新left指向1此时mid又指向1结果同上left最终指向最小值。假如mid没有先指向1或者指向7和2那么最终也会落到这些数上面重复归到上面来考虑。至此说明left最后都指向最小值。特殊情况特殊情况有两个一个是数组完全严格递增那么这种情况下right不断向左靠近直到条件终止二分left的位置始终为最小值位置。也成立另外一个是right一开始指向的就是最小值比如3、4、5、6、1这种情况下推演一下left一直往右靠近直到leftright然后这里会出现nums[mid]m的特殊情况所以这里为了保证left仍是最终答案我将这一个情况合并到了nums[mid]m,这样更新right后left仍是答案同时由于rightleft我们跳出了二分循环。这一处代码中的体现就是else{ rmid-1; }其他情况下根本判断不到nums[mid]m这种情况因为这道题是数组元素不重复只要right不在一开始指向最小值mid就不会指向m。复杂度时间复杂度: O(logN)空间复杂度: O(1)我对二分的条件分析和返回值分析总是比较复杂和费时希望各位在思考上如果有更简单的想法和思路可以告诉我。