/*
* 統計一個數字在排序數組中出現的次數。
* 注:數組已有序
*/
public class GetNumberOfK {
//算法複雜度:O(n)
public int getNumberOfK(int [] array , int k) {
int count = 0;
for(int i : array) {
if(k == i) count++;
}
return count;
}
//運用二分法查找該數第一次出現的位置和最後一次出現的位置,算法複雜度:getFirstIndex和getLastIndex的時間複雜度都是O(logn)
public int getNumberOfK2(int [] array , int k) {
if(array == null || array.length == 0) return 0;
int firstIndex = getFirstIndex(array, k, 0, array.length - 1);
int lastIndex = getLastIndex(array, k, 0, array.length - 1);
if(firstIndex != -1 && lastIndex != -1) {
return lastIndex - firstIndex + 1;
}
return 0;
}
public int getFirstIndex(int [] array, int k, int start, int end) {
if(start > end)
return -1;
int middle = (start + end) / 2;
if(array[middle] == k) {
if(middle == 0 || (middle - 1 >= 0 && array[middle - 1] != k)) {
return middle;
}
else {
end = middle - 1;
}
}
else if(array[middle] < k) {
start = middle + 1;
}
else {
end = middle - 1;
}
return getFirstIndex(array, k, start, end);
}
public int getLastIndex(int [] array, int k, int start, int end) {
if(start > end)
return -1;
int middle = (start + end) / 2;
if(array[middle] == k) {
if(middle == array.length - 1 || (middle + 1 <= array.length - 1 && array[middle + 1] != k)) {
return middle;
}
else {
start = middle + 1;
}
}
else if(array[middle] < k) {
start = middle + 1;
}
else {
end = middle - 1;
}
return getLastIndex(array, k, start, end);
}
//法三:借助字元串統計數字第一次出現的位置和最後一次出現的位置
public int getNumberOfK3(int [] array , int k) {
if(array == null || array.length == 0) return 0;
StringBuffer sb = new StringBuffer();
//System.out.println(sb);
for(int i : array) {
sb.append(i);
}
int firstIndex = sb.indexOf(k + "");
int lastIndex = sb.lastIndexOf(k + "");
//System.out.println("firstIndex:" + firstIndex + " lastIndex:" + lastIndex);
if(firstIndex < 0 || lastIndex < 0) //不存在這個數字
return 0;
return lastIndex - firstIndex + 1;
}
public static void main(String[] args) {
int [] array = {1,3,3,3,3,4,5};
GetNumberOfK t = new GetNumberOfK();
//System.out.println(t.getLastIndex(array, 3, 0, array.length - 1));
System.out.println(new GetNumberOfK().getNumberOfK3(array, 2));
}
}