題目描述

統計⼀個數字在升序數組中出現的次數。

示例1
輸⼊：[1,2,3,3,3,3,4,5],3
返回值：4

思路及解答

線性遍歷

順序遍歷數組，遇到目標值就計數

public class Solution {

    public int GetNumberOfK(int[] array, int k) {
        if (array == null || array.length == 0) {
            return 0;
        }
        
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == k) {
                count++;
            }
            // 由於數組有序，如果當前元素已大於k，可提前結束
            else if (array[i] > k) {
                break;
            }
        }
        return count;
    }
}

• 時間複雜度​：O(n)，最壞情況下需要遍歷整個數組
• ​空間複雜度​：O(1)，只使用常數級別額外空間

二分查找+左右掃描法

先使用二分查找定位到目標值，然後向兩邊擴展統計。

由於數組是有序的，可以明顯看到是二分法。

第1步是找出數值為 k 的數的索引：
假設數組為 nums[] ，⼀開始的左邊索引為 left = 0 ，右邊界索引為 right = nums.length-1

1. 將數組分成兩部分，中間的數為 nums[mid] 。第1部分為 [left,mid] ,第2部分為[mid+1,right]。
2. 如果 nums[mid]>k ,則説明 k 只可能存在前半部分中，對前半部分執⾏操作1。
3. 如果 nums[mid]<k ,則説明 k 只可能存在後半部分中，對後半部分執⾏操作1。
4. 如果 nums[mid]=k ,直接返回當前索引 mid 。
5. 如果 left > right ,説明 k 不存在，則返回 -1 。

找到索引之後，往兩邊擴展，同時統計k的個數，直到元素不等於 k 的時候停⽌。

public class Solution {

    public int GetNumberOfK(int[] array, int k) {
        if (array == null || array.length == 0) return 0;
        
        int left = 0, right = array.length - 1;
        int count = 0;
        
        // 二分查找
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (array[mid] < k) {
                left = mid + 1;
            } else if (array[mid] > k) {
                right = mid - 1;
            } else {
                // 找到目標值，向左右擴展統計
                count = 1;
                int temp = mid;
                
                // 向左統計
                while (--temp >= left && array[temp] == k) {
                    count++;
                }
                
                // 向右統計
                temp = mid;
                while (++temp <= right && array[temp] == k) {
                    count++;
                }
                break;
            }
        }
        return count;
    }
}

• ​時間複雜度​：O(log n + k)，其中k是目標值出現次數。當目標值出現次數較少時效率接近O(log n)，但最壞情況（全部是目標值）退化為O(n)
• ​空間複雜度​：O(1)

雙二分查找法（推薦）

分別使用二分查找找到目標值的起始和結束位置，計算區間長度，這是最優解法。

public class Solution {

    public int GetNumberOfK(int[] array, int k) {
        if (array == null || array.length == 0) return 0;
        
        // 找到第一個k的位置
        int firstIndex = findFirstPosition(array, k);
        // 找到最後一個k的位置
        int lastIndex = findLastPosition(array, k);
        
        if (firstIndex == -1 || lastIndex == -1) {
            return 0; // 目標值不存在
        }
        
        return lastIndex - firstIndex + 1;
    }
    
    /**
     * 查找目標值的第一個出現位置
     */
    private int findFirstPosition(int[] array, int k) {
        int left = 0, right = array.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (array[mid] < k) {
                left = mid + 1;
            } else if (array[mid] > k) {
                right = mid - 1;
            } else {
                // 關鍵：檢查是否為第一個出現位置
                if (mid == 0 || array[mid - 1] != k) {
                    return mid;
                } else {
                    right = mid - 1; // 繼續在左半部分查找
                }
            }
        }
        return -1; // 未找到
    }
    
    /**
     * 查找目標值的最後一個出現位置
     */
    private int findLastPosition(int[] array, int k) {
        int left = 0, right = array.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (array[mid] < k) {
                left = mid + 1;
            } else if (array[mid] > k) {
                right = mid - 1;
            } else {
                // 關鍵：檢查是否為最後一個出現位置
                if (mid == array.length - 1 || array[mid + 1] != k) {
                    return mid;
                } else {
                    left = mid + 1; // 繼續在右半部分查找
                }
            }
        }
        return -1; // 未找到
    }
}

• ​時間複雜度​：O(log n)，執行兩次二分查找
• ​空間複雜度​：O(1)，只使用常數空間

k±0.5邊界查找法

一種巧妙的解法，通過查找目標值邊界的插入位置來計算出現次數。

由於數組元素都是整數，k-0.5和k+0.5正好是目標值範圍的邊界，它們的插入位置差值就是目標值出現次數

public class Solution {

    public int GetNumberOfK(int[] array, int k) {
        if (array == null || array.length == 0) return 0;
        
        // 查找k+0.5的插入位置（第一個大於k的位置）
        int upperBound = findInsertPosition(array, k + 0.5);
        // 查找k-0.5的插入位置（第一個大於等於k的位置）
        int lowerBound = findInsertPosition(array, k - 0.5);
        
        return upperBound - lowerBound;
    }
    
    /**
     * 在有序數組中查找目標值的插入位置
     */
    private int findInsertPosition(int[] array, double target) {
        int left = 0, right = array.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left; // 返回插入位置
    }
}

• ​時間複雜度​：O(log n)，兩次二分查找
• ​空間複雜度​：O(1)