20200927.md

Algorithm

剑指offer-数字在升序数组中出现的次数

Description

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

Solution

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;
        }
    }

    public int getFirstK(int[] array, int k, int start, int end){
        while(start<=end){
            int mid = (start+end)/2;
            if(k<array[mid]){
                end = mid -1;
            }else if(k>array[mid]){
                start = mid +1;
            }else{
                end = mid -1;
            }
        }
        return -1;
    }

    public int getLastK(int[] array, int k, int start, int end){
        while(start<=end){
            int mid = (start+end)/2;
            if(k<array[mid]){
                end = mid-1;
            }else if(k>array[mid]){
                start = mid+1;
            }else{
                if(mid<array.length-1&&array[mid+1]!=k||mid==array.length-1){
                    return mid;
                }else{
                    start = mid+1;
                }
            }
        }
        return -1;
    }

}

Discussrs

看见有序，肯定就是二分查找了，算法比较简单，不多说，值得一提的是，不要拘泥于递归，要会循环写法。

Review

Tip

Share