Java教程

33、搜索旋转排序数组 | 算法(leetode,附思维导图 + 全部解法)300题

本文主要是介绍33、搜索旋转排序数组 | 算法(leetode,附思维导图 + 全部解法)300题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

零 标题:算法(leetode,附思维导图 + 全部解法)300题之(33)搜索旋转排序数组

一 题目描述!

题目描述
题目描述

二 解法总览(思维导图)

思维导图

三 全部解法

1 方案1

1)代码:

// 方案1 “无视要求,直接调用 indexOf 等函数”
var search = function(nums, target) {
    return nums.indexOf(target);
};

2 方案2

1)代码:

// 方案2 “无视要求,单指针”

// 技巧:
// 1)nums是有序的,然后以某个下标进行翻转。
// 2)通过观察,可以得知 新的nums 走势基本就是 “升序-降序-升序”。

// 思路(整体分2种情况):
// 1)状态初始化
// 2)分 2种 情况 。
// 2.1)若 nums[left] <= target ,则 不断判断 nums[left] === target 。
// 若 相等,则 直接返回 left,否则 left++ 。
// 2.2)若 nums[right] >= target ,则 不断判断 nums[right] === target 。
// 若 相等,则 直接返回 right,否则 right-- 。
var search = function(nums, target) {
    // 1)状态初始化
    const l = nums.length;
    let left = 0,
        right = l - 1;
    
    // 2)分 2种 情况 。
    // 2.1)若 nums[left] <= target ,则 不断判断 nums[left] === target 。
    // 若 相等,则 直接返回 left,否则 left++ 。
    if (nums[left] <= target) {
        while(left < l) {
            if (nums[left] === target) {
                return left;
            }
            left++;
        }
        return -1;
    }
    // 2.2)若 nums[right] >= target ,则 不断判断 nums[right] === target 。
    // 若 相等,则 直接返回 right,否则 right-- 。
    else if(nums[right] >= target){
        while(right >= 0) {
            if (nums[right] === target) {
                return right;
            }
            right--;
        }
        return -1;
    }

    // 边界case: [4,5,6,7,0,1,2] 3
    return -1;
}

3 方案3

1)代码:

// 方案3 “二分查找”。
// 技巧:O(log n)的时间复杂度 --> “二分查找” 。

// 参考:
// 1)https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/ji-jian-solution-by-lukelee/
var search = function(nums, target) {
    const l = nums.length;
    let left = 0,
        right = l - 1;
    
    while (left < right) {
        let mid = parseInt((left + right) / 2);
        if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid])) {
            left = mid + 1;
        }
        else {
            right = mid;
        }
    }

    return left === right && nums[left] === target ? left : -1;
};
这篇关于33、搜索旋转排序数组 | 算法(leetode,附思维导图 + 全部解法)300题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!