• 数字在排序数组中出现的次数
    • 题目
    • 解题思路

    数字在排序数组中出现的次数

    题目

    牛客网

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

    解题思路

    1. 利用二分查找,找到任意一个 k
    2. 由于 k 有多个,并且当前找到的 k 可能在任意位置。所以,在当前 k 的前后进行遍历查找
    1. public int GetNumberOfK(int[] array, int k) {
    2. if (array == null || array.length == 0) {
    3. return 0;
    4. }
    5. //二分查找
    6. int start = 0, end = array.length - 1;
    7. int t = -1;
    8. while (start < end) {
    9. int mid = (start + end) / 2;
    10. if (array[mid] == k) {
    11. t = mid;
    12. break;
    13. } else if (array[mid] > k) {
    14. end = mid - 1;
    15. } else {
    16. start = mid + 1;
    17. }
    18. }
    19. if (array[start] == k) {
    20. t = start;
    21. }
    22. if (t == -1) {
    23. return 0;
    24. }
    25. //左侧
    26. int sum = 0;
    27. int a = t;
    28. while (a >= 0 && array[a] == k) {
    29. sum++;
    30. a--;
    31. }
    32. //右侧
    33. a = t + 1;
    34. while (a < array.length && array[a] == k) {
    35. sum++;
    36. a++;
    37. }
    38. return sum;
    39. }