题目
统计一个数字在排序数组中出现的次数
解题思路
既然数组已经是有序的了，那么有两种方法
双指针
设立两个指针，一个指向数组的开头元素，另一个指向数组的末尾元素，然后两个指针同时向中间扫描，当遇到目前数字时停止扫描并记录指针所指向的位置；当左右指针完成后进行计算得出目标数字的出现次数
二分查找
利用二分查找，分别查找出目标数字的最左出现位置以及最右出现位置即可，然后计算目标数字的出现次数
AC代码
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
| public class Solution {
public int GetNumberOfK(int[] array , int k) {
if (array.length == 0) {
return 0;
}
int left = leftLoc(array, k);
int right = rightLoc(array, k);;
if (left == 0 && right == 0) {
return 0;
}
return (right - left) + 1;
}
public int rightLoc(int[] array, int k) {
int left = 0;
int right = array.length - 1;
if (left == right) {
if (array[left] == k) {
return 1;
}
return 0;
}
while (left < right) {
int mid = (left + right) / 2;
if (array[mid] == k && (mid == array.length - 1 || array[mid + 1] != k)) {
return mid;
}
if (array[mid] > k) {
right = mid;
} else {
left = mid + 1;
}
}
if (array[left] == k) {
return left;
}
return 0;
}
public int leftLoc(int[] array, int k) {
int left = 0;
int right = array.length - 1;
if (left == right) {
if (array[left] == k) {
return 1;
}
return 0;
}
while (left < right) {
int mid = (left + right) / 2;
if (array[mid] == k && (mid == 0 || array[mid - 1] != k)) {
return mid;
}
if (array[mid] >= k) {
right = mid;
} else {
left = mid + 1;
}
}
if (array[left] == k) {
return left;
}
return 0;
}
}
|