算法热题:在排序数组中查找数字 I

2021/09/10 08:26
阅读数 170

每日简短一刷,保持手感系列

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

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

提示:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

就单单看题目,这道理逻辑非常直白和简单,查到一个数字在排序数组中出现的次数,直接遍历一次统计就完了

class Solution {
    public int search(int[] nums, int target) {
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
          if (nums[i] == target) cnt++;
        }
        return cnt;
    }
}

时间复杂度 O(n),空间复杂度 O(1)

但是这不免也太简单了吧?

所以要注意提示,nums 是一个非递减数组,从题目和这个提示可以得知它是一个有序递增数组,看到有序二字就该有应激反应:二分法

不过这不是朴素二分,而是二分的变型。

按照题意我们应该利用二分找到和 target 相等的数组最左位置,然后之后有两个选择

  1. 根据这个最左位置直接往后遍历
  2. 再通过二分找到和 target 相等的数组最右位置

如果你选择第一种,其实时间复杂度还是变成了 O(n)。

所以我们选择第二种,继续利用变型的二分找到最后的位置,最终最右的位置减去最左的位置再+1得到的值就是重复的次数。

让我们看一下代码:


class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) { //空数组直接返回,不然下面 nums[left] 就抛错了。
          return 0;
        }
        int left = 0, right = len-1;
        //先二分找到最左节点
        while(left < right) {
          int mid = left + right >> 1;
          if (nums[mid] >= target) {
            right = mid;
          } else {
            left = mid + 1;
          } 
        }
        
        // 说明没找到,直接返回 0 
        if (nums[left] != target) {
          return 0;
        }
        
        int rightLeft = left;
        right = len - 1;
        //二分找到最右节点
        while (left < right) {
          int mid = left + right + 1 >> 1//二分边界处理,不然会死循环
          if (nums[mid] <= target) {
            left = mid;
          } else {
            right = mid - 1;
          }
        }

        return right - rightLeft + 1;

    }
}

相信思路还是挺简单的,但是十个二分九个错,所以二分的细节还是需要特意去画画的,不然容易出错,之后我再专门写一篇分析分析二分的变型。


一道简单题,可点击原文进行练习。

本文分享自微信公众号 - yes的练级攻略(yes_java)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部