题目
统计一个数字在排序数组中出现的次数
分析
这个解法可以用hashmap，一边遍历一遍记录出现的次数。 算法的时间复杂度是O(n)。
import java.util.HashMap;
public class Solution {
public int GetNumberOfK(int [] array , int k) {
if(array == null || array.length == 0)
return 0;
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < array.length;i++){
if(!map.containsKey(array[i])){
map.put(array[i],1);
}else{
int count = map.get(array[i]) + 1;
map.put(array[i],count);
}
}
if(map.containsKey(k)){
return map.get(k);
}else{
return 0;
}
}
}
但是这不是最优解，看到有序数组，我们自然想到二分查找，非常适合有序数组的查找，时间复杂是O(logn)。
因此，我们可以先用二分查找法找到第一个3（假如要查找3），然后以这个3为界限，向数组的前后进行继续的查找，这个时候有可能时间复杂度是O(n)，也不是最优解
那么，我们如何找到第一个和最后一个3呢，当我们用二分查找法进行查找第一个3时，假如array[mid]>3，那么最后一个3一定在中间数字的左边，假如array[mid]<3 ,那么第一个3一定在中间数的右边。如果中间数正好等于3，我们就看中间数的前一个数是否等于3，如果等于3，那么我们就要到数组的前半部分去查找3. 同理可以考虑找到最后一个3.
代码
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int length = array.length;
if (length == 0) {
return 0;
}
int firstKIndex = getFirstK(array, 0, length - 1,k );
int lastKIndex = getLastK(array, 0, length-1, k);
if (firstKIndex != -1 && lastKIndex != -1) {
return lastKIndex - firstKIndex +1;
}
return 0;
}
// 递归
public int getFirstK(int [] array,int start,int end,int k){
if (start > end) {
return -1;
}
int min = start + (end -start)/2;
if (array[min] > k) {
return getFirstK(array, start, min -1, k);
}else if (array[min]<k) {
return getFirstK(array, min + 1, end, k);
}else {
if (min - 1>=0 && array[min - 1]==k) {
return getFirstK(array, start, min - 1, k);
}else {
return min;
}
}
}
// 循环
public int getLastK(int [] array,int start,int end,int k){
if (start > end) {
return -1;
}
int min = start + (end - start)/2;
while (start <= end) {
if (array[min] > k ) {
end = min -1;
}else if (array[min] < k) {
start = min+ 1;
} else {
if (min + 1 < array.length && array[min + 1] == k ) {
start = min + 1;
}else{
return min;
}
}
min = start + (end - start)/2;
}
return 0;
}
}
