50

admin管理员组

文章数量:1123567

50

50题 第15天 搜索旋转排序数组

• 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
  ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
  搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
  你可以假设数组中不存在重复的元素。
  你的算法时间复杂度必须是 O(log n) 级别。
• 我的代码如下：

class Solution {public int search(int[] nums, int target) {if (nums.length == 0) {return -1;}int L = 0; int R = nums.length - 1;while (L <= R) {int mid = (L + R) / 2;if (nums[mid] == target) {return mid;}else if(nums[mid] >= nums[L]){if (nums[L] <= target && target < nums[mid])R = mid - 1;elseL = mid + 1;} else {if (nums[mid] < target && target <= nums[R])L = mid + 1;elseR = mid - 1;}}return -1;}
}

运行结果

• 这个题一看是新题，不像前几天的题关联都很紧密的。拿到这样的题，是怎么想的呢。要是没有花里胡哨的旋转，为了满足时间复杂度，一般会用二分法。那么直接用二分法的问题是什么呢？是因为mid未必是整个数组正常顺序的mid，但是有一部分是不变的，就是mid的前半部分与mid的后半部分总有一个是按顺序排列的。根据例子我们可以看出，首项要是比mid小的话，那说明从首项到mid是按从小到大的顺序的，即旋转长度比mid长；反之mid到尾项是从小到大的，旋转长度比mid小。按这种思路，对顺序的进行正常的二分操作（如果target在里面的话），非顺序的部分只要反过来用另一种情况就行了（反之target不在正常顺序的一部分，那就移动指针把正常顺序的一部分丢掉就好了嘛），是不是就把问题简单了。

本文标签： 50