Voyz's Studio.

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

算法题 热题HOT100 二分法
字数统计: 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. 方法一：二分法
Total : 137
2021
2020
2019
2018
技术贴 JavaScript Flutter 算法题 热题HOT100 哈希表 滑动窗口 回溯算法 链表 二分法 矩阵 动态规划 贪心算法 指针 快速排序 迭代 二叉树 数组 快慢指针 排序 背包问题 单调栈 栈 DFS 岛屿问题 React Native React 旅行记 效率工具 python 小程序 英语 生活 足球 算法 性能优化 ES6 TypeScript koa