[37] 数字在升序数组中出现的次数(中等)
[37] 数字在升序数组中出现的次数(中等)

题目描述

统计一个数字在升序数组中出现的次数。
输入:[1,2,3,3,3,3,4,5],3
返回值:4

解题思路

暴力法

直接全部遍历。
/**
 * 暴力法
 * T(n) S(1)
 */
public int GetNumberOfK(int [] array , int k) {
    int count = 0;
    for (int i : array) {
        if (i == k) {
            count++;
        }
    }
    return count;
}

双指针

头尾同时遍历。
/**
 * 双指针
 * T(n/2) S(1)
 */
public int GetNumberOfK(int [] array , int k) {
    if (array.length == 1) {
        if (array[0] == k) {
            return 1;
        } else {
            return 0;
        }
    }
    int a = 0;
    int b = array.length - 1;
    int c = 0;
    while (a < b) {
        if (array[a++] == k) {
            c++;
        }
        if (array[b--] == k) {
            c++;
        }
    }
    return c;
}

二分法

如题所述数组是升序序列,首先用二分查找向左推进找到目标数的上界(起始下标),然后再次通过二分查找向右推进找到目标数的下界(结尾下标)+ 1,然后通过上界减去下界即可得到目标数的出现次数。
/**
 * 二分法
 * T(logn) S(1)
 */
public int GetNumberOfK(int [] array , int k) {
    // 找上界
    int l = 0;
    int r = array.length;
    while (l < r)  {
        int mid = l + (r - l) / 2;
        if (array[mid] < k) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    int lBounds = l;
    // 找下界
    l = 0;
    r = array.length;
    while (l < r)  {
        int mid = l + (r - l) / 2;
        if (array[mid] <= k) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    int rBounds = l;
    return rBounds - lBounds;
}