題目描述

• 統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組里出現(xiàn)的次數(shù)料祠。例如輸入排序數(shù)組{1,2,3,3,3,3,4,5}和數(shù)字3，由于3在這個(gè)數(shù)組中出現(xiàn)了4次澎羞，因此輸出4髓绽。

解題思路

1. 可利用二分查找的方式，分別找出第一個(gè)出現(xiàn)的數(shù)字K妆绞，和最后出現(xiàn)的數(shù)字K顺呕，然后這兩個(gè)位置的下標(biāo)相減即可。
2. 若當(dāng)數(shù)組中間的數(shù)字M大于K,則第一個(gè)K肯定在數(shù)組左邊括饶。如果M小于K,則第一個(gè)K肯定在右邊株茶。如果M等于K，若M前一個(gè)數(shù)字不為K图焰，則M就是第一個(gè)K启盛。如果M前一個(gè)數(shù)字仍然等于K，則第一個(gè)K還是在左邊技羔。如此反復(fù)即可求得第一個(gè)K的位置僵闯。
3. 同理可求得最后一個(gè)K的位置。

代碼

int getNumberOfK(int[] arr, int k){
    // 求第一個(gè)K
    int first = findFirstKIndex(arr, k);
    // 求最后一個(gè)K
    int last = findLastKIndex(arr, k);
    if (first > -1 && last > -1) {
        return last - first + 1;
    }
    return -1;
}

int findFirstKIndex(int[] arr, int k) {
    if (arr == null || arr.length <=0) {
        return -1;
    }
    int start = 0;
    int end  = arr.length - 1;
    while (start <= end) {
        int middleIndex = start + (end - start) / 2;
        if (arr[middleIndex] > k) {
            end = middleIndex - 1;
        } else if (arr[middleIndex] < k) {
            start = middleIndex + 1;
        } else {
            if(middleIndex == 0 || ((middleIndex - 1) >= 0 && arr[middleIndex - 1] != k )) {
                // 若前數(shù)字不等k藤滥，則當(dāng)前位置就是第一個(gè)k
                return middleIndex;
            } else {
                end = middleIndex - 1;
            }
        }
     }
    return -1;
}
int findLastKIndex(int[] arr, int k) {
    if (arr == null || arr.length <=0) {
        return -1;
    }

    int start = 0;
    int end  = arr.length - 1;
    while (start <= end) {
        int middleIndex = start + (end - start) / 2;
        if (arr[middleIndex] > k) {
            end = middleIndex - 1;
        } else if (arr[middleIndex] < k) {
            start = middleIndex + 1;
        } else {
            if(middleIndex == arr.length - 1 || ((middleIndex + 1) < arr.length && arr[middleIndex + 1] != k )) {
                // 若后一個(gè)數(shù)字不等k鳖粟，則當(dāng)前位置就是最后一個(gè)k
                return middleIndex;
            } else {
                start = middleIndex + 1;
            }
        }
    }
    return -1;
}

題目二

• 題目描述：0 ~ n-1中缺失的數(shù)字。一個(gè)長(zhǎng)度為n-1的遞增數(shù)組中所有數(shù)字都是唯一的超陆，并且每個(gè)數(shù)的都在0 ~ n-1之內(nèi)牺弹。在范圍0~n-1內(nèi)的n個(gè)數(shù)字中有且只有一個(gè)數(shù)字不在改數(shù)組中，請(qǐng)找出該數(shù)字时呀。
• 解題思路：
  1. 因?yàn)閿?shù)組是排序的张漂，因此在這個(gè)缺失的數(shù)字之前，數(shù)組的下標(biāo)和對(duì)應(yīng)的值是相同的谨娜。
  2. 在這個(gè)缺失的數(shù)字之后航攒，數(shù)組的下標(biāo)比數(shù)組的值大。
  3. 因此可以用二分查找法趴梢，找出第一個(gè)下標(biāo)和值不相同的位置漠畜。該位置即為缺失的數(shù)字币他。