面接問題38:数字がソート配列に現れる回数


一.タイトル
1つの数値がソート配列に現れる回数を統計する.例えば、入力ソート配列{1,2,3,3,3,4,5}と数字3は、この配列に3が4回現れるため、出力4となる.
コードは私のコードライブラリにPoint 2 Offerをダウンロードしてください
二.コード#コード#
package ween_2;

/**    :***
 *   offer:              
 *   :    
 *     :    (   ,  1 ,  ,   ,   )
 *       (    ,         )
 * @author dingding
 * Date:2017-6-27 20:00
 * Declaration: All Rights Reserved!
 */
public class No38 {

    public static void main(String[] args) {
        test1();
        test2();
        test3();
        test4();
        test5();
        test6();
        test7();
    }

    //     k   
    private static int getFirstK(int[] array,int length,int k,int start,int end){
        if (start>end) {
            return -1;
        }
        int middleIndex = (start+end)/2;
        int middleData = array[middleIndex];
        if (middleData == k) {
            if ((middleIndex > 0 && array[middleIndex-1]!=k) || middleIndex==0) {
                return middleIndex;
            }else {
                end = middleIndex-1;
            }
        }else if (middleData>k) {
            end = middleIndex - 1;
        }else {
            start = middleIndex + 1;
        }

        return getFirstK(array, length, k, start, end);
    }

    //      k   
    private static int getLastK(int[] array,int length,int k,int start,int end){
        if (start>end) {
            return -1;
        }
        int middleIndex = (start+end)/2;
        int middleData = array[middleIndex];
        if (middleData==k) {
            if ((middleIndex1 && array[middleIndex+1]!=k) || middleIndex==length-1) {
                return middleIndex;
            }else {
                start = middleIndex+1;
            }
        }else if(middleData1;
        }else {
            end = middleIndex - 1;
        }

        return getLastK(array, length, k, start, end);
    }

    //       
    private static int getNumberOfK(int[] array,int length,int k){
        int number = 0;
        if (array == null || length<1) {
            return -1;
        }
        if (array != null && length>0) {
            int first = getFirstK(array, length, k, 0, length-1);
            int last = getLastK(array, length, k, 0, length-1);

            if (first>-1 && last > -1) {
                number = last - first +1;
            }
        }

        return number;
    }
    /*==================    ================*/
    private static void test(int[] array,int length,int k){
        int result = getNumberOfK(array, length, k);
        if (result != -1) {
            System.out.println(k+"      : "+ result);
        }else{
            System.out.println("      !");
        }

        System.out.println("====================");
    }
    private static void test1() {
        int[] array = {1,2,3,4,5,5,6};
        int k=7;
        test(array, array.length, k);
    }

    private static void test2() {
        int[] array = {1,2,3,4,5,5,6};
        int k=3;
        test(array, array.length, k);
    }

    private static void test3() {
        int[] array = {1,2,3,4,5,5,6};
        int k=5;
        test(array, array.length, k);
    }

    private static void test4() {
        int[] array = {1,2,3,4,5,5,6};
        int k=6;
        test(array, array.length, k);
    }

    private static void test5() {
        int[] array = {1,2,3,4,5,5,6};
        int k=1;
        test(array, array.length, k);       
    }

    private static void test6() {
        int[] array = {1};
        int k=1;
        test(array, array.length, k);       
    }

    private static void test7() {
        int[] array = {};
        int k=6;
        test(array, array.length, k);
    }

}


不適切な点がありましたら、お知らせください.