Voyz's Studio.

LeetCode算法笔记--搜索旋转排序数组

字数统计: 427阅读时长: 2 min
2020/12/10 Share

LeetCode算法笔记–Day37

31. Next Permutation

题目:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

Your algorithm’s runtime complexity must be in the order of O(log n).

example
input: nums = [4,5,6,7,0,1,2], target = 0
output: 4

My Answer:

方法一:二分法

题目要求算法时间复杂度必须是O(logn) 的级别,提示可以使用二分搜索的方法。

我们将数组从中间分开成左右两部分的时候,一定有一部分的数组是有序的。

  • 如果 [l, mid - 1] 是有序数组,且 target 的大小满足 [\textit{nums}[l],\textit{nums}[mid])[nums[l],nums[mid]),则我们应该将搜索范围缩小至 [l, mid - 1],否则在 [mid + 1, r] 中寻找。

  • 如果 [mid, r] 是有序数组,且 target 的大小满足 (\textit{nums}[mid+1],\textit{nums}[r]](nums[mid+1],nums[r]],则我们应该将搜索范围缩小至 [mid + 1, r],否则在 [l, mid - 1] 中寻找。

Runtime complexity : O(logn)
Space complexity : O(1)

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
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
let _start = 0,_end = nums.length - 1;

// 空数组返回-1
if(_end < 0) return -1;

while(_start <= _end){
let _mid = _start + ((_end-_start) >> 2);
if(nums[_mid] == target) return _mid;

// 左侧有序
if(nums[_mid] >= nums[_start]){
// target在左边区间
if(target >= nums[_start] && target < nums[_mid]){
_end = _mid - 1;
}
// target在右边区间
else{
_start = _mid + 1;
}
}
// 右侧有序
else{
// target在右边区间
if(target > nums[_mid] && target <= nums[_end]){
_start = _mid + 1;
}
// target在左边区间
else{
_end = _mid - 1;
}
}
}

// 不存在
return -1;
};
CATALOG
  1. 1. LeetCode算法笔记–Day37
  2. 2. 31. Next Permutation
    1. 2.1. 题目:
    2. 2.2. My Answer:
      1. 2.2.1. 方法一:二分法