【剑指offer】面试题53（1）：数字在排序数组中出现的次数

素颜马尾好姑娘i 2022-06-11 06:37 95阅读 0赞

## 题目 ##

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

## 思路 ##

二分法找到该数字的第一个下标，和最后一个下标  
若在数组中找到某下标对应的值为k，  
　如果它的前一个数字不为k，则它就是第一个k；  
　如果它的后一个数字不为k，则它就是最后一个k

## 代码 ##

/**
     * 题目：
     * 统计一个数字在排序数组中出现的次数。
     * 
     * 思路：
     * 二分法找到该数字的第一个下标，和最后一个下标
     * 若在数组中找到某下标对应的值为k，
     * 如果它的前一个数字不为k，则它就是第一个k；
     * 如果它的后一个数字不为k，则它就是最后一个k
     * 
     * @author peige
     */
    public class _53_01_NumberOfK {
    
        public int GetNumberOfK(int [] array , int k) {
            if(array == null || array.length == 0)
                return 0;
            int indexOfFirstK = getFirstK(array, 0, array.length - 1, k);
            int indexOfLastK = getLastK(array, 0, array.length - 1, k);
            if(indexOfFirstK == -1)
                return 0;
            return indexOfLastK - indexOfFirstK + 1;
        }
    
        private int getFirstK(int[] array, int low, int high, int k) {
            if(low > high)
                return -1;
            int mid = low + (high - low) / 2;
            if(array[mid] > k) 
                return getFirstK(array, low, mid - 1, k);
            else if(array[mid] < k)
                return getFirstK(array, mid + 1, high, k);
            else if(mid > 0 && array[mid - 1] == k) 
                return getFirstK(array, low, mid - 1, k);
            else
                return mid;
        }
    
        private int getLastK(int[] array, int low, int high, int k) {
            if(low > high)
                return -1;
            int mid = low + (high - low) / 2;
            if(array[mid] > k) 
                return getLastK(array, low, mid - 1, k);
            else if(array[mid] < k)
                return getLastK(array, mid + 1, high, k);
            else if(mid < high && array[mid + 1] == k) 
                return getLastK(array, mid + 1, high, k);
            else
                return mid;
        }
    }

## 测试 ##

public class _53_01_Test {
    
        public static void main(String[] args) {
            test1();
            test2();
            test3();
        }
    
        private static void test1() {
            int[] arr = new int[] {
       1,2,2,3,3,3,3,3,4,4,4,5,5,6,7,8};
            _53_01_NumberOfK nok = new _53_01_NumberOfK();
            int n = nok.GetNumberOfK(arr, 3);
            MyTest.equal(n, 5);
    
            n = nok.GetNumberOfK(arr, 4);
            //System.out.println(n);
            MyTest.equal(n, 3);
    
            n = nok.GetNumberOfK(arr, 5);
            //System.out.println(n);
            MyTest.equal(n, 2);
    
            n = nok.GetNumberOfK(arr, 6);
            MyTest.equal(n, 1);
    
            n = nok.GetNumberOfK(arr, 11);
            MyTest.equal(n, 0);
        }
    
        private static void test2() {
            int[] arr = new int[] {
       1};
            _53_01_NumberOfK nok = new _53_01_NumberOfK();
            int n = nok.GetNumberOfK(arr, 3);
            MyTest.equal(n, 0);
    
            n = nok.GetNumberOfK(arr, 1);
            MyTest.equal(n, 1);
        }
    
        private static void test3() {
            _53_01_NumberOfK nok = new _53_01_NumberOfK();
            int n = nok.GetNumberOfK(new int[0], 1);
            MyTest.equal(n, 0);
    
            n = nok.GetNumberOfK(null, 1);
            MyTest.equal(n, 0);
        }
    }