題目53：數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
統(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 。
思路
利用改進(jìn)的二分算法。
- 如何用二分查找算法在數(shù)組中找到第一個(gè) k，二分查找算法總是先拿數(shù)組中間的數(shù)字和 k 作比較贝润。
如果中間的數(shù)字比 k 大，那么 k 只有可能出現(xiàn)在數(shù)組的前半段铝宵，下一輪我們只在數(shù)組的前半段查找就可以了打掘。
如果中間的數(shù)字比 k 小，那么 k 只有可能出現(xiàn)在數(shù)組的后半段鹏秋，下一輪我們只在數(shù)組的后半段查找就可以了尊蚁。
如果中間的數(shù)字和 k 相等呢？
3.1 我們先判斷這個(gè)數(shù)字是不是第一個(gè) k侣夷。如果位于中間數(shù)字的前面一個(gè)數(shù)字不是 k,此時(shí)中間的數(shù)字剛好就是第一個(gè) k横朋。
3.2 如果中間數(shù)字的前面一個(gè)數(shù)字也是 k，也就是說第一個(gè) k 肯定在數(shù)組的前半段百拓， 下一輪我們?nèi)匀恍枰跀?shù)組的前半段查找琴锭。
- 同樣的思路在排序數(shù)組中找到最后一個(gè) k晰甚。
- 如果中間數(shù)字比 k 大，那么 k 只能出現(xiàn)在數(shù)組的前半段决帖。
- 如果中間數(shù)字比 k 小厕九，k 就只能出現(xiàn)在數(shù)組的后半段。
- 如果中間數(shù)字等于 k 呢地回？
3.1 我們需要判斷這個(gè) k 是不是最后一個(gè) k扁远，也就是中間數(shù)字的下一個(gè)數(shù)字是不是也等于 k。
3.2 如果下一個(gè)數(shù)字不是 k落君，則中間數(shù)字就是最后一個(gè) k 了，否則下一輪我們還是要在數(shù)組的后半段中去查找亭引。
代碼實(shí)現(xiàn)
public class _5300{
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);
}
public static int getNumberOfK(int[] data, int k) {
int number = 0;
if (data != null && data.length > 0) {
int first = getFirstK(data, k, 0, data.length - 1);
int last = getLastK(data, k, 0, data.length - 1);
if (first > -1 && last > -1) {
number = last - first + 1;
}
}
return number;
}
public static void main(String[] args) {
int[] data = {1, 2, 3, 3, 3, 3, 4, 5};
System.out.println(getNumberOfK(data, 3)); // 4
}
}
輸出
4
