Leetcode刷题(第33题)——搜索旋转排序数组

x33g5p2x  于2022-02-28 转载在 其他  
字(0.7k)|赞(0)|评价(0)|浏览(153)

一、题目

二、示例

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

示例二
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1

示例三
输入:nums = [1], target = 0
输出:-1

进阶:你可以设计一个时间复杂度为 O(log n) 的解决方案吗?
三、思路
如果按照普通查询的话,时间复杂度为O(n),如果想要事件复杂度为O(logn),则应该采用二分查找
本题中只是存在旋转排序,但是其顺序任然可以理解为整齐的。只不过需要在其中多一些逻辑判断。
四、代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1
    let flag = -1
    while(left <= right) {
        let mid = Math.floor((left + right) / 2)
        if(nums[mid] === target) {
            flag = mid
        }
        if(nums[left] <= nums[mid]) {  //旋转节点在mid以右
            if(nums[left] <= target && nums[mid] >= target) {
                right = mid - 1   
            }else {
                left = mid + 1
            }
        }else {  //旋转节点在mid以左
            if(nums[mid] <= target && nums[right] >= target ) {
                left = mid + 1
            }else{
                right = mid - 1
            }
        }
    }
    return flag
};

五、总结

相关文章

微信公众号

最新文章

更多