統計一個數字在升序陣列中出現的次數
解題思路
有序陣列一定要想到二分查找！有序陣列一定要想到二分查找！有序陣列一定要想到二分查找！
因為有序，所以目標值如果有多個，肯定是連在一起，又已知我們可以在有序陣列中查找任意一個值，因此我們可以先查找目標范圍的下界和上界，
上界定義為：指向最后一個目標值，
下界定義為：指向第一個目標值，
public class Solution {
public int GetNumberOfK(int[] array , int k) {
if(array == null || array.length == 0) {
return 0;
}
int firstK = getFirstKey(array, k, 0, array.length - 1);
int lastK = getLastKey(array, k, 0, array.length - 1);
if(firstK != -1 && lastK != -1) {
return lastK - firstK + 1;
}
return 0;
}
// 遞回寫法
public int getFirstKey(int[] array, int k, int start, int end) {
if(start > end) {
return -1;
}
int mid = (start + end) >> 1;
if(array[mid] > k) {
return getFirstKey(array, k, start, mid - 1);
} else if(array[mid] < k) {
return getFirstKey(array, k, mid + 1, end);
} else if(mid - 1 >= 0 && array[mid - 1] == k) {
return getFirstKey(array, k, start, mid - 1);
} else {
return mid;
}
}
// 回圈寫法
public int getLastKey(int[] array, int k, int start, int end) {
int len = array.length;
int mid = (start + end) >> 1;
while(start <= end) {
if(array[mid] > k) {
end = mid - 1;
} else if(array[mid] < k) {
start = mid + 1;
} else if(mid + 1 < len && array[mid + 1] == k) {
start = mid + 1;
} else {
return mid;
}
mid = (start + end) >> 1;
}
return -1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/182766.html
標籤：其他