题目描述
统计一个数字在排序数组中出现的次数。
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int GetNumberOfK(int[] array, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int i : array) {
if (map.containsKey(i)) {
map.put(i, map.get(i) + 1);
} else {
map.put(i, 1);
}
}
if (map.containsKey(k)) {
return map.get(k);
} else {
return 0;
}
}
|
网上题解
链接：https://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2?answerType=1&f=discussion
来源：牛客网
有序数组应该想到二分查找
这道题目思路挺简单的，就是先二叉搜索找一下这个元素的位置，然后再开始遍历搜索一下。
本来想自己写一个二叉搜索函数的，但是转念一下java中有排序，还是用一下吧，这样代码就简洁很多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| import java.util.Arrays;
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int index = Arrays.binarySearch(array, k);
if(index<0)return 0;
int cnt = 1;
for(int i=index+1; i < array.length && array[i]==k;i++)
cnt++;
for(int i=index-1; i >= 0 && array[i]==k;i--)
cnt++;
return cnt;
}
}
|