1. 首页

LeetCode 033. 搜索旋转排序数组

题目描述

给你一个升序排列的整数数组 nums ,和一个整数 target 。

假设按照升序排序的数组在预先未知的某个点上进行了旋转。(例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

 
示例 1:

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

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

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

提示:

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
nums 肯定会在某个点上旋转
-10^4 <= target <= 10^4

难度:Middle

前置知识

  • 数组
  • 二分法

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这是一个我在网上看到的前端头条技术终面的一个算法题。

题目要求时间复杂度为logn,因此基本就是二分法了。 这道题目不是直接的有序数组,不然就是easy了。

首先要知道,我们随便选择一个点,将数组分为前后两部分,其中一部分一定是有序的。

具体步骤:

  • 我们可以先找出mid,然后根据mid来判断,mid是在有序的部分还是无序的部分

假如mid小于start,则mid一定在右边有序部分。
假如mid大于等于start, 则mid一定在左边有序部分。

注意等号的考虑

  • 然后我们继续判断target在哪一部分, 我们就可以舍弃另一部分了

我们只需要比较target和有序部分的边界关系就行了。 比如mid在右侧有序部分,即[mid, end]
那么我们只需要判断 target >= mid && target <= end 就能知道target在右侧有序部分,我们就
可以舍弃左边部分了(start = mid + 1), 反之亦然。

我们以([6,7,8,1,2,3,4,5], 4)为例讲解一下:

search-in-rotated-sorted-array-1

search-in-rotated-sorted-array-1

关键点解析

  • 二分法
  • 找出有序区间,然后根据target是否在有序区间舍弃一半元素

Js中文网 – 前端进阶资源教程 www.javascriptC.com,typescript 中文文档
Javascript中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js……等,以帮助开发者成长为愿景的社区

代码

  • 语言支持: Javascript,Python3
/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:前端中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * @lc app=leetcode id=33 lang=javascript
 *
 * [33] Search in Rotated Sorted Array
 */
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  // 时间复杂度:O(logn)
  // 空间复杂度:O(1)
  // [6,7,8,1,2,3,4,5]
  let start = 0;
  let end = nums.length - 1;

  while (start <= end) {
    const mid = start + ((end - start) >> 1);
    if (nums[mid] === target) return mid;

    // [start, mid]有序

    // ️⚠️注意这里的等号
    if (nums[mid] >= nums[start]) {
      //target 在 [start, mid] 之间

      // 其实target不可能等于nums[mid], 但是为了对称,我还是加上了等号
      if (target >= nums[start] && target <= nums[mid]) {
        end = mid - 1;
      } else {
        //target 不在 [start, mid] 之间
        start = mid + 1;
      }
    } else {
      // [mid, end]有序

      // target 在 [mid, end] 之间
      if (target >= nums[mid] && target <= nums[end]) {
        start = mid + 1;
      } else {
        // target 不在 [mid, end] 之间
        end = mid - 1;
      }
    }
  }

  return -1;
};

Python3 Code:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        """用二分法,先判断左右两边哪一边是有序的,再判断是否在有序的列表之内"""
        if len(nums) <= 0:
            return -1

        left = 0
        right = len(nums) - 1
        while left < right:
            mid = (right - left) // 2 + left
            if nums[mid] == target:
                return mid

            # 如果中间的值大于最左边的值,说明左边有序
            if nums[mid] > nums[left]:
                if nums[left] <= target <= nums[mid]:
                    right = mid
                else:
                    # 这里 +1,因为上面是 <= 符号
                    left = mid + 1
            # 否则右边有序
            else:
                # 注意:这里必须是 mid+1,因为根据我们的比较方式,mid属于左边的序列
                if nums[mid+1] <= target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid

        return left if nums[left] == target else -1

复杂度分析

更多题解可以访问我的 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 033. 搜索旋转排序数组

链接:https://www.javascriptc.com/4393.html

« LeetCode 034. 在排序数组中查找元素的第一个和最后一个位置
uni-app页面之间的传参,让下一个页面接收上一个页面的值»
Flutter 中文教程资源

相关推荐

QR code