LeetCode 33 - Search in Rotated Sorted Array

作者 QIFAN 日期 2017-02-13
LeetCode 33 - Search in Rotated Sorted Array

原题链接: [33. Search in Rotated Sorted Arrayhttps://leetcode.com/problems/search-in-rotated-sorted-array/]


题干

假设有个数组初始为升序,经过 n 次 rotate 后,寻找一个 target 。

思路

本质还是二叉查找。先找到二叉找到 pivot ,再二叉找 target 。本来想一边确定 pivot 一遍找 target ,但这样找到 pivot 后暂时没想到怎么样去改变递归中的策略,而且不管怎样 worst case 都是 $O(N)$ ,average case 是 $log(N)$ ,那就简单点。

小坑在和后一个数比较时要取余。

代码:

int pivot = -1;
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
findPivot(nums, 0, nums.length - 1);
if (target > nums[pivot] || target < nums[(pivot + 1) % nums.length]) {
return -1;
}
if (target >= nums[0] && target <= nums[pivot]) {
return binarySearch(nums, target, 0, pivot);
} else if (target <= nums[nums.length - 1]){
return binarySearch(nums, target, pivot + 1, nums.length - 1);
} else {
return -1;
}
}
private void findPivot(int[] nums, int lo, int hi) {
if (lo > hi || pivot != -1) {
return;
}
int mid = lo + (hi - lo) / 2;
if (isPivot(nums, mid)) {
pivot = mid;
} else {
findPivot(nums, lo, mid - 1);
if (pivot == -1) {
findPivot(nums, mid + 1, hi);
}
}
}
private boolean isPivot(int[] nums, int index) {
int nextIndex = (index + 1) % nums.length;
return nums[index] >= nums[nextIndex];
}
private int binarySearch(int[] nums, int target, int lo, int hi) {
if (lo > hi) {
return -1;
}
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
return binarySearch(nums, target, mid + 1, hi);
}
return binarySearch(nums, target, lo, mid - 1);
}