• 软件:1160
  • 资讯:41601|
  • 收录网站:97880|

IT精英团

421,在排序数组中查找元素的第一个和最后一个位置-对二分法查找的改造

421,在排序数组中查找元素的第一个和最后一个位置-对二分法查找的改造

浏览次数:
评论次数:
编辑: 乐咏
信息来源: 51CTO博客
更新日期: 2021-06-13 00:18:14
摘要

421,在排序数组中查找元素的第一个和最后一个位置-对二分法查找的改造,Beingborninaduckyarddoesnotmatter,ifonlyyouarehatchedfromaswan'segg. 只要是从天鹅蛋孵出来的,即使生在养鸭场也没有关系。问题描述给定一个按照升序排列的整数数组nums,和一个目标值target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是O(logn)

  • 资讯详情

Being born in a duck yard does not matter, if only you are hatched from a swan's egg. 

只要是从天鹅蛋孵出来的,即使生在养鸭场也没有关系。

问题描述

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

你的算法时间复杂度必须是 O(log n) 级别。

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

示例 1:

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

target = 8

输出: [3,4]

示例 2:

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

target = 6

输出: [-1,-1]

二分法查找

题中说了是升序的数组,也就是排过序的,对于排过序的数组查找我们

很容易想到的就是二分法。这里要返回的是目标值在数组中的开始位置和结束位置,因为相同的数字在排序数组中肯定是挨着的,所以我们通过二分法查到之后,还要往前和往后继续查找,直到不等于目标值为止。

如果是做Android的并且经常看源码的可能知道,Android中有个类ArrayMap,他存储的时候hash值是排过序的,查找的时候也是通过二分法查找,但有可能hash值会有冲突,所以他查找之后也是分别往前和往后继续查找然后再比较key值,和这题解法很相似。我们来画个简图看一下

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

比如我们通过二分法查找7,然后还要往他的前面和后面继续查找,目的是要找到最开始7和最后7的位置,来看下代码

 1public int[] searchRange(int[] nums, int target) {
2    int find = searchRangeHelper(nums, target);
3    //如果没找到,返回{-1, -1}
4    if (find == -1)
5        return new int[]{-1, -1};
6    int left = find - 1;
7    int right = find + 1;
8    //查看前面是否还有target
9    while (left >= 0 && nums[left] == target)
10        left--;
11    //查看后面是否还有target
12    while (right < nums.length && nums[right] == target)
13        right++;
14    return new int[]{left + 1, right - 1};
15}
16
17//二分法查找
18public int searchRangeHelper(int[] nums, int target) {
19    int low = 0;
20    int high = nums.length - 1;
21    while (low <= high) {
22        int mid = low + (high - low) / 2;
23        int midVal = nums[mid];
24        if (midVal < target) {
25            low = mid + 1;
26        } else if (midVal > target) {
27            high = mid - 1;
28        } else {
29            return mid;
30        }
31    }
32    return -1;
33}

二分法的另一种写法

二分查找一般我们找到某个值之后会直接返回。其实我们有时候还可以对二分法进行改造,当查找某个值的时候不直接返回,而是要继续查找,直到左右两个指针相遇为止。像下面这样,代码中有详细的注释,可以看一下

 1public int[] searchRange(int[] nums, int target) {
2    //查找第一个出现的target
3    int first = searchRangeHelper(nums, target);
4    //判断有没有查找到
5    if (first < nums.length && nums[first] == target) {
6        //如果查找到了,说明有这个值,我们再来查(target + 1),如果有这个值,
7        //那么查找的结果也是第一次出现的(target + 1)的下标,我们减去1,就是target
8        //最后一次出现的下标。如果没有(target + 1)这个值,那么查找的结果就是第一个
9        // 大于target的下标,我们减去1也是target最后一次出现的下标。所以这里
10        // 无论有没有(target + 1)这个值,都不影响
11        int last = searchRangeHelper(nums, target + 1) - 1;
12        return new int[]{first, last};
13    } else {
14        //没有找到这个值,直接返回{-1, -1}
15        return new int[]{-1, -1};
16    }
17}
18
19//如果数组nums中有多个target,那么返回值就是第一个出现的target的下标
20//如果数组nums中没有target,那么返回的就是第一个大于target的下标
21public static int searchRangeHelper(int[] nums, double target) {
22    int low = 0, high = nums.length - 1;
23    while (low <= high) {
24        int m = low + (high - low) / 2;
25        if (target > nums[m])
26            low = m + 1;
27        else
28            high = m - 1;
29    }
30    return low;
31}

看到这里可能有的同学灵光乍现,通过二分法能找到target第一次出现的位置,那么通过二分法能不能找到target最后一次出现的位置。当然也是可以的,代码在下面给你准备好了

 1public int[] searchRange(int[] nums, int target) {
2    int first = searchFirst(nums, target);
3    //判断有没有查找到
4    if (first < nums.length && nums[first] == target) {
5        int last = searchLast(nums, target);
6        return new int[]{first, last};
7    } else {
8        //没有找到这个值,直接返回{-1, -1}
9        return new int[]{-1, -1};
10    }
11}
12
13//如果数组nums中有多个target,那么返回值就是第一个出现的target的下标
14//如果数组nums中没有target,那么返回的就是第一个大于target的下标
15public static int searchFirst(int[] nums, double target) {
16    int low = 0, high = nums.length - 1;
17    while (low <= high) {
18        int m = low + (high - low) / 2;
19        if (target > nums[m])
20            low = m + 1;
21        else
22            high = m - 1;
23    }
24    return low;
25}
26
27public static int searchLast(int[] nums, double target) {
28    int low = 0, high = nums.length - 1;
29    while (low <= high) {
30        int m = low + (high - low) / 2;
31        if (target >= nums[m])
32            low = m + 1;
33        else
34            high = m - 1;
35    }
36    return high;
37}

总结

以前对二分法的查找,我们是找到之后就返回。但如果有多个重复的值,我们是没法确定返回的是哪个值的下标。今天这里我们对二分法进行了改造,如果有多个重复的值,你想返回第一个值或者最后一个值的下标都是可以的。

419,剑指 Offer-旋转数组的最小数字
« 上一篇
返回列表
下一篇 »
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
你会是第一个来这里评论的人吗?
最近发布资讯
更多