Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

搜索旋转排序数组

Posted on Edited on In , ,
Symbols count in article: 2.7k Reading time ≈ 2 mins.

来源Leetcode第33题搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

二分查找I

这道题目怎么说呢，一开始只是头铁，想试试遍历，结果还真过了，用时1ms，内存消耗36.4MB，我傻了，代码就不附了。

这题其实就是变了花样的二分查找，但是我一开始脑子抽了先对这个数组进行排序，我在想啥呢- -
这题可以先设置左右两个指针，只有当nums[right]target时返回-1，因为这时候找不到这样的数；如果nums[left]target，右指针-1。
这样写的话，怎么看也都是很普通的查找啊，连二分查找都算不上，时间复杂度我也不会算。。。。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
public int search(int[] nums, int target) {
    int length=nums.length,left=0,right=length-1;
    while(left<=right){
        if(nums[right]<target&&nums[left]>target)
            return -1;
        if(nums[left]==target) return left;
        if(nums[right]==target) return right;
        if(nums[left]<target) left++;
        else if(nums[right]>target) right--;
    }
    return -1;
}

二分查找II

评论区里的解答稍好些，考虑的情况更加具体：
同样是left、mid、right

  • 如果nums[mid] < nums[right]
    • nums[mid] < target && target <= nums[right]
      • left = mid+1
    • 否则的话就是
      • right = mid-1
  • 如果nums[left] <= target && target < nums[mid]
    • right = mid-1
    • 否则left = mid+1

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int search2(int[] nums, int target) {
    int length=nums.length,left=0,right=length-1;
    while(left<=right){
        int mid = (left + right)/2;
        if(nums[mid] == target) return mid;
        else if(nums[mid] < nums[right]){
            if(nums[mid] < target && target <= nums[right])
                left = mid+1;
            else
                right = mid-1;
        }else{
            if(nums[left] <= target && target < nums[mid])
                right = mid-1;
            else
                left = mid+1;
        }
    }
    return -1;
}

二分查找III

官方题解是先找到旋转点，在根据旋转点判断，具体思路就不写了，直接附代码吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
  int [] nums;
  int target;

  public int find_rotate_index(int left, int right) {
    if (nums[left] < nums[right])
      return 0;

    while (left <= right) {
      int pivot = (left + right) / 2;
      if (nums[pivot] > nums[pivot + 1])
        return pivot + 1;
      else {
        if (nums[pivot] < nums[left])
          right = pivot - 1;
        else
          left = pivot + 1;
      }
    }
    return 0;
  }

  public int search(int left, int right) {
    /*
    Binary search
    */
    while (left <= right) {
      int pivot = (left + right) / 2;
      if (nums[pivot] == target)
        return pivot;
      else {
        if (target < nums[pivot])
          right = pivot - 1;
        else
          left = pivot + 1;
      }
    }
    return -1;
  }

  public int search(int[] nums, int target) {
    this.nums = nums;
    this.target = target;

    int n = nums.length;

    if (n == 0)
      return -1;
    if (n == 1)
      return this.nums[0] == target ? 0 : -1;

    int rotate_index = find_rotate_index(0, n - 1);

    // if target is the smallest element
    if (nums[rotate_index] == target)
      return rotate_index;
    // if array is not rotated, search in the entire array
    if (rotate_index == 0)
      return search(0, n - 1);
    if (target < nums[0])
      // search in the right side
      return search(rotate_index, n - 1);
    // search in the left side
    return search(0, rotate_index);
  }
}

另外一篇的极简Solution，脑壳疼，先摸了