今天和大家聊的问题叫做 搜索旋转排序数组 II,我们先来看题面:
https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/...题意
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。...我们当然可以退一步采用遍历的方法去寻找切分点,但是既然如此,我们为什么不直接去寻找答案呢?反正都已经是O(n)的复杂度了。所以这是行不通的,我们想要使得复杂度维持在
?
就必须要寻找其他的路数。...想明白这点之后就简单了,看起来很像是递归,但实际上它的本质仍然是二分。代码并不难写,但是还有一个问题没解决,就是当nums[m] = nums[l]的时候,我们如何判断是哪一种情况呢?...答案是没法判断,两种情况都有可能,对于这种情况也没有很好的办法,我想出来的办法是可以将l向右移动一位,相当于抛弃了一个最左侧的数。