首页 > 其他分享 >LeetCode题练习与总结:在排序数组中查找元素的第一个和最后一个位置

LeetCode题练习与总结:在排序数组中查找元素的第一个和最后一个位置

时间:2024-03-14 20:58:05浏览次数:28  
标签:二分 right 复杂度 查找 数组 目标值 排序 LeetCode

一、题目

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

二、解题思路

1. 查找起始位置

  • 使用二分查找确定目标值是否存在于数组中,并找到其第一次出现的位置。
  • 如果目标值不存在,直接返回 [-1, -1]。
  • 如果目标值存在,记录这个位置作为起始位置。

2. 查找结束位置

  • 由于数组是有序的,我们可以从起始位置开始,向右进行二分查找,但是这次我们寻找的是目标值最后一次出现的位置。
  • 我们需要调整二分查找的逻辑,使其在找到目标值后继续向右查找,直到找不到目标值为止。

三、具体代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = -1, right = -1;
        int len = nums.length;
        
        // 查找起始位置
        int mid = 0;
        while (mid < len) {
            if (nums[mid] == target) {
                left = mid;
                break;
            } else if (nums[mid] < target) {
                mid += (len - mid) / 2;
            } else {
                len = mid;
            }
        }
        
        // 如果没有找到目标值,直接返回 [-1, -1]
        if (left == -1) {
            return new int[]{left, right};
        }
        
        // 查找结束位置
        right = left;
        len = nums.length;
        while (right < len) {
            int pos = right + (len - right) / 2;
            if (nums[pos] == target) {
                right = pos;
                len = pos;
            } else {
                right = pos + 1;
            }
        }
        
        return new int[]{left, right};
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度
  • 时间复杂度是 O(log n)。
  • 查找起始位置的二分查找操作是 O(log n),因为每次迭代都将搜索范围减半。
  • 查找结束位置的二分查找操作同样是 O(log n),原因同上。
  • 两个二分查找操作是独立的,所以总的时间复杂度是 O(log n) + O(log n) = O(log n)。
2. 空间复杂度
  • 空间复杂度是 O(1)。
  • 代码中没有使用额外的数据结构来存储数据,所有的变量都是局部变量,其空间需求与输入数组的大小无关。
  • 因此,空间复杂度是 O(1),即常数空间复杂度。

五、总结知识点

1. 二分查找(Binary Search)

  • 二分查找是一种在有序数组中查找特定元素的高效算法。
  • 它通过将目标值与数组中间元素进行比较,根据比较结果缩小搜索范围,直到找到目标值或搜索范围为空。

2. 循环结构

  • 使用 while 循环来实现二分查找的迭代过程。
  • 循环条件和迭代逻辑是二分查找算法的核心部分。

3. 条件判断

  • 在二分查找过程中,使用 if-else 语句来判断数组中间元素与目标值的关系,从而决定是向左半部分还是向右半部分继续查找。

4. 变量初始化与更新

  • 初始化 leftright 变量为 -1,表示目标值的起始和结束位置未找到。
  • 在查找过程中,根据查找结果更新这些变量的值。

5. 数组操作

  • 使用数组索引来访问和比较数组中的元素。

6. 返回值

  • 返回一个包含两个整数的数组,分别表示目标值的起始和结束位置。
  • 如果目标值不存在于数组中,则返回 [-1, -1]。

7. 边界条件处理

  • 在查找结束位置时,需要特别处理边界条件,确保不会访问数组的无效索引。

8. 算法效率

  • 代码实现了 O(log n) 的时间复杂度,这是二分查找算法的典型时间复杂度。
  • 空间复杂度为 O(1),因为除了输入数组外,没有使用额外的空间。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

标签:二分,right,复杂度,查找,数组,目标值,排序,LeetCode
From: https://blog.csdn.net/weixin_62860386/article/details/136427939

相关文章

  • 『LeetCode』10. 正则表达式匹配 Regular Expression Matching
    题目描述给你一个字符串s和一个字符规律p,请你来实现一个支持'.'和'*'的正则表达式匹配。'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素所谓匹配,是要涵盖整个字符串s的,而不是部分字符串。示例1:输入:s="aa",p="a"输出:false解释:"a"无法匹配"aa"整个字......
  • LeetCodeHot100 73. 矩阵置零 54. 螺旋矩阵 48. 旋转图像 240. 搜索二维矩阵 II
    73.矩阵置零https://leetcode.cn/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-100-likedpublicvoidsetZeroes(int[][]matrix){inttop=0,bottom=matrix.length,left=0,right=matrix[0].length;int[][]flag......
  • Java中的Map集合如何根据key值排序?
    Java中的Map集合如何根据key值排序(HashMap<String,Object>)?Map集合的键(key)默认是按照它们的hashCode排序的,这在有时间不符合业务排序。如果你想要根据Map的key值进行排序,一般以下有几种方法可以实现。方法一:使用TreeMap使用TreeMap类,它会自动根据key的自然顺序或自定义比较器......
  • LeetCode232.栈实现队列
    ques:用两个栈实现队列功能ans:与225一样的思路,看完225大佬们的题解之后能很轻松的想出思路,用s1来实现真正模拟队列中的元素顺序,借助s2辅助完成这一排序代码实现#include<iostream>#include<stack>usingnamespacestd;classMyQueue{private:stack<int>s1;/......
  • leetcode.21 合并两个有序链表
     21.合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1,1,2,3,4,4]示例2:输入:l1=[],l2=[]输出:[]示例3:输入:l1=[],l2=[0]输......
  • 经典排序算法回顾:
    排序算法有非常多,应用也非常多,在各种笔试面试中也常常出现,所以现在就来复习一下相关的排序算法吧!下面会介绍多种排序算法,在此之前先说一下,排序算法的评价主要有以下几个方面:排序算法的时间复杂度;排序算法的空间复杂度;排序算法的稳定性其中前两个是老生常谈了,基本提到算法都会考虑......
  • 14_学习日志_数据结构_冒泡排序_快速排序_插入排序
    #include<编织有意义的谎言,使我相信闭上眼再睁开眼时的世界是同一个>1.介绍    从后往前或者从前往后开始两两比较元素,使得最小数上浮或者最大数下沉为冒泡排序,快速排序利用分治思想,使得基准数左边都存放相对较小数,右边存放较大数,两边再按照同样的做法重复。插入排序......
  • [LeetCode] 2789. Largest Element in an Array after Merge Operations
    Youaregivena0-indexedarraynumsconsistingofpositiveintegers.Youcandothefollowingoperationonthearrayanynumberoftimes:Chooseanintegerisuchthat0<=i<nums.length-1andnums[i]<=nums[i+1].Replacetheelementnums......
  • Java(计算机相关)面试之海量数据问题处理(1)分治/hash/排序
    原文链接:https://blog.csdn.net/a619602087/article/details/130348569面试的时候经常被问到海量数据处理问题,下面我会分期介绍几种海量数据处理的思路还有案例了解了之后面试不用怕了大数据处理思路:分而治之/Hash映射+HashMap统计+堆/快速/归并排序分而治之/hash映射:......
  • 【算法】二分查找——BinarySearch
    一、概述二分查找又称折半查找,是一种能够大幅减少时间复杂度的查找方法,但是二分查找要求线性表必须词用顺序储存结构,而且表中元素按关键字有序排列。在后续讨论中,我们假设有序表递增有序。二分查找中使用的术语:目标Target——你要查找的值索引Index——你要查找的当前......