Java和C++如何在排序数组中查找数字出现的次数

这篇文章主要介绍“Java和C++如何在排序数组中查找数字出现的次数”，在日常操作中，相信很多人在Java和C++如何在排序数组中查找数字出现的次数问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Java和C++如何在排序数组中查找数字出现的次数”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

1、题目

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

示例 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 <= 10^5

• -10^9 <= nums[i] <= 10^9

• nums 是一个非递减数组

• -10^9 <= target <= 10^9

2、思路

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

样例：

如样例所示，nums = [5,7,7,8,8,10]，target = 8，8在数组中出现的次数为2，于是最后返回2。

数组有序，因此可以使用二分来做。两次二分，第一次二分查找第一个>= target的位置begin；第二次二分查找最后一个<= target的位置end，查找成功则返回end - begin + 1，即为数字在排序数组中出现的次数，否则返回0，表示该数没有在数组中出现。

二分模板：

模板1

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1，计算mid时不需要加1，即mid = (l + r)/2。

C++/java代码模板：

int bsearch_1(int l, int r){    while (l < r)    {        int mid = (l + r)/2;        if (check(mid)) r = mid;        else l = mid + 1;    }    return l;}

模板2

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid，此时为了防止死循环，计算mid时需要加1，即mid = ( l + r + 1 ) /2。

C++/java 代码模板：

int bsearch_2(int l, int r){    while (l < r)    {        int mid = ( l + r + 1 ) /2;        if (check(mid)) l = mid;        else r = mid - 1;    }    return l;}

为什么两个二分模板的mid取值不同？

对于第二个模板，当我们更新区间时，如果左边界l更新为l = mid，此时mid的取值就应为mid = (l + r + 1)/ 2。因为当右边界r = l + 1时，此时mid = (l + l + 1)/2，相当于下取整，mid为l，左边界再次更新为l = mid = l，相当于没有变化。while循环就会陷入死循环。因此，我们总结出来一个小技巧，当左边界要更新为l = mid时，我们就令 mid =(l + r + 1)/2，相当于上取整，此时就不会因为r取特殊值r = l + 1而陷入死循环了。

而对于第一个模板，如果左边界l更新为l = mid + 1，是不会出现这样的困扰的。因此，大家可以熟记这两个二分模板，基本上可以解决99%以上的二分问题，再也不会被二分的边界取值所困扰了。

什么时候用模板1？什么时候用模板2？

假设初始时我们的二分区间为[l,r]，每次二分缩小区间时，如果左边界l要更新为 l = mid，此时我们就要使用模板2，让 mid = (l + r + 1)/ 2，否则while会陷入死循环。如果左边界l更新为l = mid + 1,此时我们就使用模板1，让mid = (l + r)/2。因此，模板1和模板2本质上是根据代码来区分的，而不是应用场景。如果写完之后发现是l = mid，那么在计算mid时需要加上1，否则如果写完之后发现是l = mid + 1，那么在计算mid时不能加1。

为什么模板要取while( l < r)，而不是while( l <= r)？

本质上取l < r 和 l <= r是没有任何区别的，只是习惯问题，如果取l <= r，只需要修改对应的更新区间即可。

while循环结束条件是l >= r，但为什么二分结束时我们优先取r而不是l?

二分的while循环的结束条件是l >= r，所以在循环结束时l有可能会大于r，此时就可能导致越界，二分问题我们优先取r。

二分查找的实现细节：

二分查找时，首先要确定我们要查找的边界值，保证每次二分缩小区间时，边界值始终包含在内。

注意看下面的每张图，最后的答案就是红色箭头指出的位置，也是我们二分的边界值。如果不清楚每次二分时，区间是如何更新的，可以画出和下面类似的图，每次更新区间时，要保证边值始终包含在内，这样关于左右边界的更新就会一目了然。

第一次查找target起始位置:

二分的范围，l = 0， r = nums.size() - 1，我们去二分查找>= target的最左边界begin。

当nums[mid] >= target时，往左半区域找，r = mid。

当nums[mid] < target时， 往右半区域找，l = mid + 1。

如果nums[r] != target，说明数组中不存在目标值 target，返回 0。否则我们就找到了第一个>=target的位置begin。

第二次查找target结束位置：

二分的范围，l = 0， r = nums.size() - 1，我们去二分查找<= target的最右边界end。

当nums[mid] <= target时，往右半区域找，l = mid。

当nums[mid] > target时， 往左半区域找，r = mid - 1。

找到了最后一个<= target的位置begin，返回end - begin + 1即可。

时间复杂度分析： 两次二分查找的时间复杂度为 O ( l o g n ) O(logn)O(logn)。

空间复杂度分析： 没有使用额外的数组，因此空间复杂度为O ( 1 ) O(1)O(1)。

3、c++代码

class Solution {public:    int search(vector<int>& nums, int target) {        if(!nums.size()) return  0;        int l = 0, r = nums.size() - 1;        while(l < r)       //查找target的开始位置        {            int mid = (l + r) / 2;            if(nums[mid] >= target) r = mid;            else l = mid + 1;        }        if(nums[r] != target) return 0 ;  //查找失败        int begin = r;     //记录开始位置        l = 0, r = nums.size() - 1;        while(l < r)       //查找tatget的结束位置        {            int mid = (l + r + 1) / 2;            if(nums[mid] <= target) l = mid;            else r = mid - 1;        }        int end = r;       //记录结束位置              return end - begin + 1;    } };

4、java代码

class Solution {    public int search(int[] nums, int target) {        if(nums.length == 0) return  0;        int l = 0, r = nums.length - 1;        while(l < r)       //查找target的开始位置        {            int mid = (l + r) / 2;            if(nums[mid] >= target) r = mid;            else l = mid + 1;        }        if(nums[r] != target) return 0 ;  //查找失败        int begin = r;     //记录开始位置        l = 0; r = nums.length - 1;        while(l < r)       //查找tatget的结束位置        {            int mid = (l + r + 1) / 2;            if(nums[mid] <= target) l = mid;            else r = mid - 1;        }        int end = r;       //记录结束位置              return end - begin + 1;      }}

到此，关于“Java和C++如何在排序数组中查找数字出现的次数”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注编程网网站，小编会继续努力为大家带来更多实用的文章！