【牛客 - 剑指offer】JZ53 数字在升序数组中出现的次数 Java实现

---

剑指offer题解汇总 Java实现

https://blog.csdn.net/guliguliguliguli/article/details/126089434

本题链接

知识分类篇 - 02 算法 - 搜索算法 - JZ53 数字在升序数组中出现的次数 Java实现

题目

方案一 暴力

public class Solution {
    public int GetNumberOfK(int[] array, int k) {

        int cnt = 0;
        for (int i : array) {
            if (i == k) {
                cnt++;
            }
        }
        return cnt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

方案二 二分（推荐）

分治

分治即“分而治之”

• “分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的问题，子问题继续按照这样划分，直到问题可以被轻易解决
• “治”指的是将子问题单独进行处理

经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现

思路

因为data是一个非降序数组，它是有序的，这种时候可以想到用二分查找。但是一个数组可能有多个k，要查找的并非常规的二分法中k的位置，而是k出现的左界和右界。如果能找到销号小于k的数字和恰好大于k的数字就可以了

再者，数组中全是整数，因此可以考虑，用二分查找找到k+0.5和k-0.5应该出现的位置

具体做法

1. 写一个二分查找的函数在数组中找到某个元素出现的位置。每次检查区间中点值，根据与区间中点的大小比较，确定下一次的区间。

2. 分别使用二分查找，找到k-0.5和k+0.5应该出现的位置，中间的部分就全是k，相减计算次数就OK

public class Solution {

    public int GetNumberOfK(int[] array, int k) {
        return binarySearch(array, k + 0.5) - binarySearch(array, k - 0.5);
    }

    public int binarySearch(int[] array, double k) {
        int left = 0;
        int right = array.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (k > array[mid]) {
                left = mid + 1;
            } else if (k < array[mid]) {
                right = mid - 1;
            }
        }
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1. while循环的条件必须设置为left <= right，不然，当数组只有一个数的时候，进不去while循环

2. 让数组中的mid位置的值大于k时，right必须重新赋值为mid-1，不能赋值为mid，因为在数组中只有一个数的时候，且要查找的k就是数组中这个数的时候，只是把mid赋值给left或者right时，会出现死循环

例如 [3]，3 这个例子