力扣：53 - I 在排序数组中查找数字 I

发表于

「这是我参与11月更文挑战的第11天，活动详情查看：2021最后一次更文挑战」

描述

统计一个数字在排序数组中出现的次数。

  • 示例 1:
1
2
ini复制代码输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
  • 示例 2:
1
2
ini复制代码输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
  • 提示
1
2
3
4
diff复制代码0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
  • 进阶：
  • 如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

解析

由题目可知，在排序数组中，寻找target，是否在数组存在，已经存在的次数；如果没有存在就返回0,否则就返回存在的次数。

直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 \textit{target}target 的下标，但这个方法的时间复杂度为 O(n)O(n)，没有利用到数组升序排列的条件。

由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。

如果存在target在数组中存在，那么他在数组中可以用下标给标示出来，那么我们可以找出数组中target出现的左边界left和有边界right,即返回的次数就是right-left-1。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
ini复制代码class Solution {
    public int search(int[] nums, int target) {
       //获取数组长度
       int length=nums.length;
       //因为这个数组里面的数字是排序好的，
       //所以通过二分法来确定target对应在数组中出现的区域，区域内都是target值
       int i=0;
       int j=length-1;
        //先确定目标区域的右边界
       while(i<=j){
           int m=(i+j)/2;
           //if存在说明target所在范围在二分法的右边
           if(nums[m]<=target){
               i=m+1;
           }else{
               j=m-1;
           }
       }
​
       int right=i;
       if(j>0&&nums[j]!=target){
           return 0;
       }
       i=0;j=length-1;
       //确定目标的左边界
       while(i<=j){
           int m=(i+j)/2;
           //target的左边界必然小于target的值
           if(nums[m]<target){
               i=m+1;
           }else{
               j=m-1;
           }
       }
       int left=j;
        //右区间-左区间-1 就是含的个数
       return right-left-1;
    }
}
​

运行结果：

执行结果：通过

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：41.1 MB, 在所有 Java 提交中击败了81.55%的用户

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%