【IT笔试面试题整理】数字在排序数组中出现的次数

【试题描述】统计一个数字在排序数组中出现的次数。例如输入的排序数组{1, 2, 3, 3, 3, 3, 4, 5}

和数字3,由于3在这个数组中出现了4次,因此输出4。

【试题来源】未知

【参考代码】

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int GetFirstK(int array[], int length, int start, int end, int k) {

if(start > end) {
return -1; //No Found
}

int middle = (start + end) / 2;
if(array[middle] == k) {

if((middle > 0 && array[middle - 1] != k)
|| middle == 0) {
return middle;
} else {
end = middle - 1;
}
} else if(array[middle] < k) {
start = middle + 1;
} else {
end = middle - 1;
}

return GetFirstK(array, length, start, end, k);
}

int GetLastK(int array[], int length, int start, int end, int k) {

if(start > end) {
return -1; //No Found
}

int middle = (start + end) / 2;
if(array[middle] == k) {

if((middle < length - 1 && array[middle + 1] != k)
|| middle == length - 1) {
return middle;
} else {
start = middle + 1;
}
} else if(array[middle] < k) {
start = middle + 1;
} else {
end = middle - 1;
}

return GetLastK(array, length, start, end, k);
}

int GetNumOfK(int array[], int length, int k) {

if(array == NULL || length <= 0) {
throw ("Invalid input.");
}

int first = GetFirstK(array, length, 0 , length - 1, k);
int last = GetLastK(array, length, 0 , length - 1, k);

if(first > -1 && last > -1) {
return last - first + 1;
}

return -1;
}