刷题

在排序数组中查找数字 I

scorlw 发布于

在排序数组中查找数字 I

关键词：二分法、个数统计与查找

题目描述

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

示例 1：

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

示例2：

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

解法

解法一：

思路：

  • 题目的主要目的是查找target的左右边界。
  • 查找可以使用二分法。
  • 两次二分，分别查找左右边界。

算法流程：

  1. 初始化i、j为左右边界；
  2. 分别查找左右边界

代码：

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
int search(vector<int> &nums, int target)
{
    if (nums.size() <= 0 || target < nums[0] || target > nums[nums.size() - 1]) return 0;
    int i = 0, j = nums.size() - 1;
    int m = 0;
    //查找右边界
    while(i  <= j){
        m = (i + j) / 2;
        if(nums[m] <= target){//此时右边界如果存在，则在m-j之间
            i = m + 1;
        }
        else{
            j = m - 1;//此时右边界如果存在，则在i-m之间
        }
    }
    if(j >= 0 && nums[j] != target) return 0;//判断target是否真的存在
    int right = i;//保存右边界
    //查找左边界，与上同理
    j = i, i = 0;//j直接初始化为右边界
    while (i <= j)
    {
        m = (i + j) / 2;
        if(nums[m] < target){
            i = m + 1;
        }
        else{
            j = m - 1;
        }
    }
    int left = j;
    
    return right - left - 1;
}

解法二：

思路：

可以将查找左边界转换为查找target-1的右边界，封装查找右边界的函数。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int helper(vector<int> &nums, int target)
{
    int i = 0, j = nums.size() - 1;
    while (i <= j)
    {
        int m = (i + j) / 2;
        if (nums[m] <= target)
        {
            i = m + 1;
        }
        else
        {
            j = m - 1;
        }
    }
    return i;
}

int search(vector<int> &nums, int target)
{
    return helper(nums, target) - helper(nums, target - 1);
}

知识点

  1. 二分法
  2. 个数统计转化为查找。