37、数字在排序数组中出现的次数

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

感觉这题应该可以用hashmap做（O(n)），也可以用二分查找做（O(logn)？）

import java.util.*;
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0; i<array.length; i++){
            if(map.get(array[i])==null){
                map.put(array[i],1);
            }else{
                int tmp = map.get(array[i]);
                map.put(array[i],tmp+1);
            }
        }
        return map.get(k)==null?0:map.get(k);
    }
}

2017.6.13 二分查找实现

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int number = 0;
        if (array != null && array.length > 0) {
            int first = getFirstK(array, k, 0, array.length - 1);
            int last = getLastK(array, k, 0, array.length - 1);
            if (first > -1 && last > -1) {
                number = last - first + 1;
            }
        }
        return number;
    }
    
    private static int getFirstK(int[] data, int k, int start, int end) {
        if (data == null || data.length < 1 || start > end) {
            return -1;
        }
        int midIdx = start + (end - start) / 2;
        int midData = data[midIdx];
        if (midData == k) {
            if (midIdx > 0 && data[midIdx - 1] != k || midIdx == 0) {
                return midIdx;
            } else {
                end = midIdx - 1;
            }
        } else if (midData > k) {
            end = midIdx - 1;
        } else {
            start = midIdx + 1;
        }
        return getFirstK(data, k, start, end);
    }
    
    private static int getLastK(int[] data, int k, int start, int end) {
        if (data == null || data.length < 1 || start > end) {
            return -1;
        }
        int midIdx = start + (end - start) / 2;
        int midData = data[midIdx];
        if (midData == k) {
            if (midIdx + 1 < data.length && data[midIdx + 1] != k || midIdx == data.length - 1) {
                return midIdx;
            } else {
                start = midIdx + 1;
            }
        } else if (midData < k) {
            start = midIdx + 1;
        } else {
            end = midIdx - 1;
        }
        return getLastK(data, k, start, end);
    }
}

2017.6.14

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array==null||array.length==0){
            return 0;
        }
       int start = 0;
       int end = array.length-1;
       int first = GetFirstK(array,start,end,k);
       int last = GetLastK(array,start,end,k);
        if(first!=-1&&last!=-1){
            return last-first+1;
        }
        return 0;
        
    }
    
    public static int GetFirstK(int [] array, int start, int end, int k){
        if(start>end){
            return -1;
        }
        int mid = start + (end-start)/2;
        if(array[mid]==k){
            if(mid==0||array[mid-1]<k){
                return mid;
            }else{
                end = mid-1;
                return GetFirstK(array, start, end, k);
            }
        }else if(array[mid]<k){
            start = mid+1;
            return GetFirstK(array, start, end, k);
        }else{
            end = mid-1;
            return GetFirstK(array, start, end, k);
        }
    }
    
    public static int GetLastK(int [] array, int start, int end, int k){
        if(start>end){
            return -1;
        }
        int mid = start + (end-start)/2;
        if(array[mid]==k){
            if(mid==array.length-1||array[mid+1]>k){
                return mid;
            }else{
                start = start+1;
                return GetLastK(array, start, end, k);
            }
        }else if(array[mid]<k){
            start = mid+1;
            return GetLastK(array, start, end, k);
        }else{
            end = mid-1;
            return GetLastK(array, start, end, k);
        }
    }
}