ACM 选手图解 LeetCode 查找元素在排序数组的区间位置

简介: ACM 选手图解 LeetCode 查找元素在排序数组的区间位置

大家好呀,我是帅蛋。


今天解决在排序数组中查找元素的第一个和最后一个位置,这道题和我们之前做的二分查找又有些区别。


这次要查找的数组虽然也是升序的整数数组,但是它存在重复的元素


下面就让我们一起来看一下这样的题怎么解,直接开始。

640.png



 LeetCode 34:排序数组首尾元素



题意


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


如果 target 不在数组中,返回 [-1,-1]


示例


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

输出:[3,4]


提示


  • 0 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums 是一个非递减数组
  • -10^9 <= target <= 10^9


题目解析


难度中等,二分查找经典好题。


到目前为止,我们已经做了两道二分查找的题:


ACM 选手图解 LeetCode 算术平方根这道题:整数数组 nums 有序、无重复、target 能在数组中找到


ACM 选手图解 LeetCode 搜索插入位置这道题:整数数组 nums 有序、无重复、target 不一定能在数组中找到


而本题则是:整数数组 nums 有序、有重复、target 不一定能在数组中找到


nums 存在重复的元素,这就意味着在 nums 数组中二分查找 target 返回的下标不唯一的。


但幸运的是 nums 有序。

640.jpg


就算有重复元素,重复元素也是挨在一起的,挨在一起就存在区间,本题就是查找 target 在 nums 中的区间,即查找 target 在 nums 中的左右边界。


仔细想的话,要找 target 在 nums 数组中的左右边界,无非存在 3 种情况


  • target 在 nums[0] ~ nums[n-1] 中,nums 中存在 target。例如 nums = [5,7,7,8,8,10],target = 8,返回 [3,4]。
  • target 在 nums[0] ~ nums[n-1] 中,nums 中不存在 target。例如 nums = [5,7,7,8,8,10],target = 6,返回 [-1,-1]。
  • target < nums[0] 或者 target > nums[n-1]。例如 nums = [5,7,7,8,8,10], target = 4,返回 [-1,-1]。


为了照顾初学者,这道题我不炫技,用最简单易懂的方式来让大家理解。

640.jpg

用两个二分查找,一个二分查找查找左边界,另一个查找右边界,分情况讨论上述的 3 种情况。


下面来看图解。


图解


nums = [5,7,7,8,8,10], target = 8 为例。


首先判断 target 的范围:

if len(nums) == 0 or nums[0] > target or nums[-1] < target:
    return [-1,-1]

此例中,target = 8,在 nums[0] ~ nums[n-1] 返回内,下面开始寻找左右边界。


第一步:寻找左边界。


1. 初始化 low 和 high 指针。

640.png

low, high = 0, len(nums) - 1

2. low = 0,high = 5,mid = low + (high - low) // 2 = 2:640.png

mid = low + (high - low) // 2

此时 nums[mid] = 7 < target,所以 low 向右移动至 mid + 1 = 3 处

640.png

if nums[mid] < target:
    low = mid + 1

3. low = 3,high = 5,mid = low + (high - low) // 2 = 4:

640.png


此时 nums[mid] = 8 == target,所以 high 向左移动至 mid - 1 = 3 处

640.png

if nums[mid] == target:
    high = mid - 1

的代码是找左边界的精髓所在。


普通二分查找是,当 nums[mid] == target 时,直接返回 mid,而在本题中,则是要继续向左查找,看是否还有和 target 相等的数组元素

640.jpg


4.  low = 3,high = 3,mid = low + (high - low) // 2 = 3:

640.png


此时 nums[mid] = 8 == target,所以 high 向左移动至 mid - 1 = 2 处:

640.png

此时 low > high,while 循环中止,此时的 nums[low] == target,所以左边界为 low = 3。

640.png

if nums[low] == target:
    return low


第二步:寻找右边界。


1. 初始化 low 和 high 指针。

640.png

low, high = 0, len(nums) - 1


2. low = 0,high = 5,mid = low + (high - low) // 2 = 2:

640.png

mid = low + (high - low) // 2


此时 nums[mid] = 7 < target,所以 low 向右移动至 mid + 1 = 3 处:

640.png


if nums[mid] < target:
    low = mid + 1


3. low = 3,high = 5,mid = low + (high - low) // 2 = 4:

640.png

此时 nums[mid] = 8 == target,所以 low 向右移动至 mid + 1 = 4 处:

640.png

if nums[mid] == target:
    low = mid + 1


同样,上面的代码是找右边界的精髓所在,一直向右找,看是否还有和 target 相等的数组元素


4.  low = 4,high = 4,mid = low + (high - low) // 2 = 4:

640.png


此时 nums[mid] = 8 == target,所以 low 向右移动至 mid + 1 = 5 处:

640.png



此时 low > high,while 循环中止,此时的 nums[high] == target,所以右边界为 high = 4。

640.png

if nums[high] == target:
    return high


此时左右边界都已找到,至此结束,返回 [3,4]。

640.png

本题解使用二分查找,一共执行两次,所以时间复杂度为 O(logn)


除了几个指针外,并无占用其它空间,所以空间复杂度为 O(1)


代码实现


Python 代码实现


class Solution:
    # 寻找左边界
    def leftMargin(self, nums: List[int], target: int):
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = low + (high - low) // 2
            # 如果 nums[mid] = target,继续向左寻找左边界
            if nums[mid] == target:
                high = mid - 1
            elif nums[mid] > target:
                high = mid - 1
            else:
                low = mid + 1
        if nums[low] == target:
            return low
        # 如果左边界的值不等于 target
        else:
            return -1
    # 寻找右边界
    def rightMargin(self, nums: List[int], target: int):
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = low + (high - low) // 2
            # 如果 nums[mid] = traget,继续向右寻找右边界
            if nums[mid] == target:
                low = mid + 1
            elif nums[mid] > target:
                high = mid - 1
            else:
                low = mid + 1
        if nums[high] == target:
            return high
        # 如果右边界的值不等于 target
        else:
            return -1
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if len(nums) == 0 or nums[0] > target or nums[-1] < target:
            return [-1,-1]
        lm = self.leftMargin(nums, target)
        rm = self.rightMargin(nums, target)
        return [lm,rm]

Java 代码实现


class Solution {
    public int leftMargin(int[] nums,int target){
        int low = 0;
        int high = nums.length - 1;
        while(low <= high){
            int mid = low + (high-low)/2;
            if(nums[mid] < target){
                low = mid + 1;
            }else if(nums[mid] > target){
                high = mid - 1;
            }else if(nums[mid] == target){
                high = mid - 1;
            }
        }
        if (nums[low] == target) {
            return low;
        } else {
            return -1;
        }
    }
    public int rightMargin(int[] nums,int target){
        int low = 0;
        int high = nums.length - 1;
        int rm = -2;
        while(low <= high){
            int mid = low + (high-low)/2;
            if(nums[mid] < target){
                low = mid + 1;
            }else if(nums[mid] > target){
                high = mid - 1;
            }else if(nums[mid] == target){
                low = mid + 1;
                rm = low;
            }
        }
        if (nums[high] == target) {
            return high;
        } else {
            return -1;
        }
    }
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0 || nums[0] > target || nums[nums.length - 1] < target) {
            return new int[] {-1,-1};
        }
        int lm = leftMargin(nums,target);
        int rm = rightMargin(nums,target);
        return new int[] {lm,rm};
    }
}

图解元素在排序数组的区间位置到这就结束辣,自认为写的很清楚了,是不是收获满满?


到目前为止三道二分查找的实战题,解决了三种不同情况的数组,自己要仔细揣摩差别。


二分查找就这些东西,在边界和细节上搞人,只要每次做题小心点,就没啥问题。

640.jpg

如果对这道题还有什么问题,可以在留言区留言。


当然不要忘了三连呀,点赞 + 在看 + 转发


我是帅蛋,我们下次见喽。


相关文章
|
15天前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
30 1
|
21天前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
29 0
|
26天前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
37 0
|
22天前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
17 4
|
21天前
|
算法
Leetcode第57题(插入区间)
LeetCode第57题“插入区间”的解题方法,包括题目描述、示例、算法思路和代码实现,旨在解决将新区间插入有序且不重叠的区间列表中,并合并重叠区间的问题。
14 0
Leetcode第57题(插入区间)
|
21天前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
13 0
Leetcode第三十三题(搜索旋转排序数组)
|
21天前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
47 0
|
21天前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
13 0
|
22天前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
27 0
|
22天前
【LeetCode-每日一题】移除元素
【LeetCode-每日一题】移除元素
29 0