題目描述
統計一個數字在排序陣列中出現的次數，
牛客網鏈接
java代碼
//看見有序就用二分法
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int len = array.length;
if (len == 0) return 0;
int low = getFirst(array, k, 0, len-1);
int high = getEnd(array, k, 0, len-1);
if (low != -1 && high != -1) return high - low + 1;
return 0;
}
//遞回
private int getFirst(int [] array, int k, int low, int high) {
if (low > high) return -1;
int mid = (low + high) >> 1;
if (array[mid] > k) return getFirst(array, k, low, mid-1);
else if (array[mid] < k) return getFirst(array, k, mid+1, high);
else if (mid-1>=0 && array[mid-1] == k) return getFirst(array, k, low, mid-1);
else return mid;
}
//回圈
private int getEnd(int[] array, int k, int low, int high) {
int mid = (low + high) >> 1;
while (low <= high) {
if (array[mid] < k) low = mid+1;
else if (array[mid] > k) high = mid-1;
else if (mid + 1 < array.length && array[mid + 1] == k) low = mid+1;
else return mid;
mid = (low + high) >> 1;
}
return -1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/127181.html
標籤：其他