[剑指offer] 数字在排序数组中出现的次数

题目描述

统计一个数字在排序数组中出现的次数。

解题思路

正常的思路就是二分查找了,我们用递归的方法实现了查找k第一次出现的下标,用循环的方法实现了查找k最后一次出现的下标。

除此之外,还有另一种奇妙的思路,因为data中都是整数,所以我们不用搜索k的两个位置,而是直接搜索k-0.5和k+0.5这两个数应该插入的位置,然后相减即可。

参考代码

法一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int len = array.length;
if(len == 0)
return 0;
int first = getFirst(array, k, 0, len-1);
int last = getLast(array, k, 0, len-1);
if(first != -1 && last != -1){
return last - first + 1;
}
return 0;
}

public int getFirst(int [] array, int k, int start, int end){
int mid;
while(start <= end){
mid = start + (end - start) / 2;
if(k <= array[mid])
end = mid - 1;
else
start = mid + 1;
}
if(start < array.length && array[start] == k)
return start;
else
return -1;
}
// 循环
public int getLast(int [] array, int k, int start, int end){
int mid;
while(start <= end){
mid = start + (end - start) / 2;
if(k >= array[mid])
start = mid + 1;
else
end = mid - 1;
}
if(end >= 0 && array[end] == k)
return end;
else
return -1;
}
}

法二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public int GetNumberOfK(int [] array , int k) {
return biSearch(array, k+0.5) - biSearch(array, k-0.5);
}
public int biSearch(int [] array, double k){
int start = 0, end = array.length - 1;
while(start <= end){
int mid = start + (end - start)/2;
if(array[mid] > k){
end = mid - 1;
}else{
start = mid + 1;
}
}
return start;
}
}