在排序数组中查找元素的第一个和最后一个位置(Java详解)

简介: 在排序数组中查找元素的第一个和最后一个位置(Java详解)

一、题目描述

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

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

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

示例:

输入:nums = [5,7,7,8,8,10],target = 8

输出:[3, 4]

输入:nums = [5,7,7,8,8,10],target = 6

输出:[-1, -1]

输入:nums = [ ],target = 0

输出:[-1, -1]

二、题解

思路分析:

题目要求我们找到出现target的第一个位置和最后一个位置,首先,我们想到可以通过暴力枚举的方法来解决该问题,即遍历数组,并记录target第一次出现和最后一次出现的位置。然而,题目要求我们实现时间复杂度为O(log n)的算法,且题目中给出的数组为非递减的数组,因此,我们可以考虑使用二分查找的方法来解决该问题

由于题目中数据量较小,使用遍历的方法也可以通过该题

遍历代码:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = -1;
        int last = -1;
        boolean flg = false;//判断是否是第一个位置
        for (int i = 0; i < nums.length; i++) {
            //第一个位置
            if(nums[i] == target && !flg){
                first = i;
                flg = true;
            }
            //最后一个位置
            //注意处理特殊情况,即最后一个元素在最后一个位置时,nums[i+1]越界
           if(nums[i] == target && (i == nums.length - 1 || nums[i+1] != target)){
                last = i;
            }
        }
        int[] ret = {first,last};
        return ret;
    }
}

如何使用二分查找来解决该问题?

题目要求我们找到target在数组中第一次出现和最后一次出现的位置,利用数组非递减的性质

首先我们查找元素的第一个位置:

我们可通过target将数组分为两部分

其中,左边部分为小于target的元素,右边部分为大于等于target的元素,由于右边区域大于等于target,因此区域最左边的值即为target第一次出现的位置,即右边区域的左端点为所求结果

我们定义left指向0位置,right指向最后一个元素,mid指向中间位置

若mid指向的元素落在右边区间,此时nums[mid]大于等于target,需要更新right的值,由于要找的结果(target第一次出现的位置)在此区间内,即mid所指向的位置可能就是最终结果,因此不能将right更新为mid - 1,而应更新为mid

若mid所指向的元素落在左边区间,此时nums[mid]小于target,需要更新 left 的值,由于要找的结果不在此区间内,因此可将left的结果更新为 mid + 1

当left和right之间元素为偶数个时,此时中间元素有两个,应该选择哪一个作为中间元素?

由于我们查找的是右边区间内最左边的元素,因此,应该选择左边的元素作为中间元素

若选择右边元素作为中间元素,能够成功查找到结果吗?

当选择右边元素作为中间元素时,此时会出现死循环的情况,例如:

上图中,当选择右边元素作为中间元素时,mid指向的元素落在右边区间,此时将right更新为mid,再求mid,此时mid仍为指向刚才位置,即落在右边区间,此时再次更新right为mid,再次求mid... 从而死循环

循环条件如何设置?

由于我们将right更新为mid,因此循环的条件应为left < right,若循环条件设置为left <= right,当left = right时,此时找到结果,而结果落在右边区间,此时会更新right的值,而right 更新为mid,即当前位置,从而死循环

分析完以上问题后,我们可以尝试编写查找右边区域最左边元素的代码:

//查找target第一次出现的位置(右边区间的左端点)
int left = 0,right = nums.length - 1,mid = left + (right - left)/2;
//循环条件应设置为left < right 
//不能设置为left <= right,否则会死循环
while(left < right){
    //当mid所指向的元素落在左边区间时,更新left
    if(nums[mid] < target){
        left = mid + 1;
    }else{//当mid所指向的元素落在右边区间时,此时更新right
        //由于右边区间的元素大于等于target,即结果在该区间内,
        // 因此不能将right更新为mid - 1,而应更新为mid
        right = mid;
    }
    //更新mid,当有两个中间元素时,mid应指向其中左边的元素
    mid = left + (right - left) / 2;
}

此时我们查找target最后一次出现的位置

与查找第一次出现位置的思路相同,我们首先将数组分为两个部分:

其中,左边区间内元素小于等于target,右边区间元素大于target

此时,要找的结果即为左边区间的右端点

同样的,定义left指向0位置,right指向最后一个元素,mid指向中间位置

若mid所指向的元素落在左边区间,此时需要更新left的值,由于要找的结果落在此区间内,即mid所指向的位置可能就是最终结果,因此不能将left更新为mid + 1,而应更新为mid

若mid所指向的元素落在右边区间,此时需要更新right的值,由于要找的结果不在右边区间,因此可将right的值更新为mid - 1

当left和right之间元素为偶数个时,此时中间元素有两个,应该选择哪一个作为中间元素?

由于我们查找的是左边区间内最右边的元素,因此,应该选择右边的元素作为中间元素

mid = left + (right - left + 1) / 2;

同样的,当选择左边元素作为中间元素时,也会造成死循环

此时left的值一直更新为当前位置,造成死循环

循环条件的设置:

循环条件也同样应该设置为left < right,否则会死循环

此时我们尝试编写查找左边区间右端点代码:

//查找区间右端点
left = mid;
right = nums.length - 1;
mid = left + (right - left + 1)/2;
while(left < right){
    //当mid所指向的值落在右边区域时,更新右端点
    if(nums[mid] > target){
        right = mid - 1;
    }else{//当mid所指向的值落在左边区域时,更新左端点
        //由于左边区间的元素小于等于target,即结果在该区间内,
        //因此不能将left更新为mid + 1,而应更新为mid
        left = mid;
    }
    //更新mid的值,若有两个中间元素时,mid应指向其中右边的元素
    mid = left + (right - left + 1) / 2;
}

完整代码:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = {-1,-1};
         //若数组为空,直接返回ret
        if(nums.length == 0){
            return ret;
        }
        //查找target第一次出现的位置(右边区间的左端点)
        int left = 0,right = nums.length - 1,mid = left + (right - left) / 2;
        //循环条件应设置为left < right
        //不能设置为left <= right,否则会死循环
        while(left < right){
            //当mid所指向的元素落在左边区间时,更新left
            if(nums[mid] < target){
                left = mid + 1;
            }else{//当mid所指向的元素落在右边区间时,此时更新right
                //由于右边区间的元素大于等于target,即结果在该区间内,
                // 因此不能将right更新为mid - 1,而应更新为mid
                right = mid;
            }
            //更新mid,当有两个中间元素时,mid应指向其中左边的元素
            mid = left + (right - left) / 2;
        }
        //此时left = right = mid,使用哪一个变量进行判断和更新都可以
        //若数组中无值为target的元素,直接返回ret
        if(nums[left] == target){
            ret[0] = left;
        }else{
            return ret;
        }
        //查找区间右端点
        left = mid;
        right = nums.length - 1;
        mid = left + (right - left + 1)/2;
        while(left < right) {
            //当mid所指向的值落在右边区域时,更新右端点
            if (nums[mid] > target) {
                right = mid - 1;
            } else {//当mid所指向的值落在左边区域时,更新左端点
                //由于左边区间的元素小于等于target,即结果在该区间内,
                //因此不能将left更新为mid + 1,而应更新为mid
                left = mid;
            }
            //更新mid的值,若有两个中间元素时,mid应指向其中右边的元素
            mid = left + (right - left + 1) / 2;
        }
        ret[1] = left;
        return ret;
    }
}

题目来自:

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)

目录
相关文章
|
5天前
|
人工智能 Java
Java练习题-输出二维数组对角线元素和
Java练习题-输出二维数组对角线元素和
17 1
|
21天前
|
Java
java实现向有序数组中插入一个元素
java实现向有序数组中插入一个元素
8 0
|
14天前
|
Java
java 8 数组转字符串并以逗号分隔
java 8 数组转字符串并以逗号分隔
10 0
|
21天前
|
Java
【Java】数组中的拷贝方法与初步理解深浅拷贝
【Java】数组中的拷贝方法与初步理解深浅拷贝
12 0
|
21天前
|
存储 Java C语言
【Java】以数组为例简单理解引用类型变量
【Java】以数组为例简单理解引用类型变量
11 1
|
22天前
|
存储 Java 索引
Java数组
Java数组
7 0
|
23天前
|
Java
java中判断数组中元素出现的次数
java中判断数组中元素出现的次数
8 0
|
23天前
|
Java
java向数组中插入元素
java向数组中插入元素
8 0
|
3月前
|
前端开发 Java
java前端:删除数组中指定元素的方法
java前端:删除数组中指定元素的方法
|
25天前
|
Java 索引
JAVA数组的常用方法
JAVA数组的常用方法
15 1