【劍指Offer】數字在排序數組中出現的次數

數字在排序數組中出現的次數

題目描述

統計一個數字在排序數組中出現的次數。

方法一：直接周遊，計數

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       int count = 0;
       for(int i = 0; i < array.length; i++) {
           if(array[i] == k) {
               count++;
           }
       }
       return count;
    }
}
           

方法二：排序數組，想到二分法

因為有序，想到二分查找。找到待查找值在數組中第一次、最後一次出現的位置，兩個位置相減，即為待查找值出現的次數

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array == null || array.length == 0)
            return 0;
        int first = getFirstK(array,k,0,array.length - 1);
        int last = getLastK(array,k,0,array.length - 1);
        if(first == -1 || last == -1)
            return 0;
        else
            return last - first + 1;
    }
    private int getFirstK(int [] array, int k, int low, int high){
        int mid = 0;
        while(low <= high){
            mid = low + (high - low) / 2;
            if(array[mid] == k){
                if(mid > 0 && array[mid - 1] != k || mid == 0)
                    return mid;
                else
                    high = mid - 1;
            }
            else if(array[mid] > k)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
    private int getLastK(int [] array, int k, int low, int high){
        int mid = 0;
        while(low <= high){
            mid = low + (high -low) / 2;
            if(array[mid] == k){
                if(mid < array.length - 1 && array[mid + 1] != k || mid == array.length - 1)
                    return mid;
                else
                    low = mid + 1;
            }
            else if(array[mid] > k)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
}
           

連結：https://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2?f=discussion

來源：牛客網