题目描述
统计一个数字在排序数组中出现的次数。
解题思路
注意这个数组是有序的，对于有序数组的查找一半选用二分查找法。
例如，要查找的数字为 k ，取数组中间位置的元素 mid ，若 k < mid, 说明要查的 k 在数组的前半段，继续在前半段进行二分查找；若 k==mid 则查找成功；否则在数组后半段采用二分查找。
本题需要查找数字在数组中出现的次数，只需找到这个数字的第一个位置，和最后一个位置，通过下标即可求得次数。
时间复杂度为 O(logn)。
代码
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
64
65
66
| class Solution
{
public:
int GetNumberOfK(vector<int> data ,int k)
{
if (data.size() == 0)
return 0;
int first = FirstPost(data, k, 0, data.size() - 1);
int end = EndPost(data, k, 0, data.size() - 1);
if (first != -1 && end != -1)
return (end - first + 1);
return 0;
}
int FirstPost(vector<int> data, int k, int begin, int end)
{
if (begin > end)
return -1;
int mid = (end + begin)/2;
int midData = data[mid];
if (midData == k)
{
if ((mid > 0 && data[mid - 1] != k) || mid == 0)
return mid;
else
end = mid - 1;
}
else if (midData > k)
end = mid - 1;
else
begin = mid + 1;
return FirstPost(data, k, begin, end);
}
int EndPost(vector<int> data, int k, int begin, int end)
{
int mid = (begin + end)/2;
int midData = data[mid];
while (begin <= end)
{
if (midData == k)
{
if ((mid < data.size() - 1 && data[mid + 1] != k) || mid == data.size() - 1)
return mid;
else
begin = mid + 1;
}
else if (midData > k)
end = mid - 1;
else
begin = mid + 1;
mid = (begin + end)/2;
midData = data[mid];
}
return -1;
}
};
|
其中 获得第一次的位置可以使用循环的方法得到，同样最后一次的位置也可用递归的方法得到。
参考博文链接：https://cuijiahua.com/blog/2018/01/basis_37.html