题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1，2，3，3，3，3，4，5}和数字3，由于3在这个数组中出现了4次，因此输出4.
找到排序数组中的第一个K：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
int
GetFirstK(
int
*data,
int
length,
int
k,
int
start,
int
end)
{
if
(start > end)
return
-1;
int
middleIndex = start + ((end - start) >> 1);
int
middleData = data[middleIndex];
if
(middleData == k)
{
if
((middleIndex > 0 && data[middleIndex - 1] != k) || middleIndex == 0)
return
middleIndex;
else
end = middleIndex - 1;
}
else
if
(middleData > k)
end = middleIndex - 1;
else
start = middleIndex + 1;
return
GetFirstK(data, length, k, start, end);
}
|
找到排序数组中最后一个k：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
int
GetLastK(
int
*data,
int
length,
int
k,
int
start,
int
end)
{
if
(start > end)
return
-1;
int
middleIndex = start + ((end - start) >> 1);
int
middleData = data[middleIndex];
if
(middleData == k)
{
if
((middleIndex < length - 1 && data[middleIndex + 1] != k) || middleIndex == length -1)
return
middleIndex;
else
start = middleIndex + 1;
}
else
if
(middleData < k)
start = middleIndex + 1;
else
end = middleIndex - 1;
return
GetLastK(data, length, k, start, end);
}
|
在分别找到第一个k和最后一个k的下标之后，就能计算出k在数组中出现的次数了。相应的代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int
GetNumberOfK(
int
*data,
int
length,
int
k)
{
int
number = 0;
if
(data != NULL && length > 0)
{
int
first = GetFirstK(data, length, k, 0, length - 1);
int
last = GetLastK(data, length, k, 0, length - 1);
if
(first > -1 && last > -1)
number = last - first + 1;
}
return
number;
}
|
完整代码如下：
|
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
|
int
GetFirstK(
int
*data,
int
length,
int
k,
int
start,
int
end)
{
if
(start > end)
return
-1;
int
middleIndex = start + ((end - start) >> 1);
int
middleData = data[middleIndex];
if
(middleData == k)
{
if
((middleIndex > 0 && data[middleIndex - 1] != k) || middleIndex == 0)
return
middleIndex;
else
end = middleIndex - 1;
}
else
if
(middleData > k)
end = middleIndex - 1;
else
start = middleIndex + 1;
return
GetFirstK(data, length, k, start, end);
}
int
GetLastK(
int
*data,
int
length,
int
k,
int
start,
int
end)
{
if
(start > end)
return
-1;
int
middleIndex = start + ((end - start) >> 1);
int
middleData = data[middleIndex];
if
(middleData == k)
{
if
((middleIndex < length - 1 && data[middleIndex + 1] != k) || middleIndex == length -1)
return
middleIndex;
else
start = middleIndex + 1;
}
else
if
(middleData < k)
start = middleIndex + 1;
else
end = middleIndex - 1;
return
GetLastK(data, length, k, start, end);
}
int
GetNumberOfK(
int
*data,
int
length,
int
k)
{
int
number = 0;
if
(data != NULL && length > 0)
{
int
first = GetFirstK(data, length, k, 0, length - 1);
int
last = GetLastK(data, length, k, 0, length - 1);
if
(first > -1 && last > -1)
number = last - first + 1;
}
return
number;
}
|
本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/p/3642322.html，如需转载请自行联系原作者
