05-数字在排序数组中出现的次数
ALEX CODE PARK 2020-02-11
算法
数组
# 题目描述
统计一个数字在排序数组中出现的次数。
# 思路分析
- 通过 indexOf 和 lastIndexOf 查找边界
- 二分查找边界
# 代码实现
function findBou(arr, num, mode) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
let mid = Math.floor((left + right) / 2);
console.log(arr, left, right, mid);
if (arr[mid] < num) {
left = mid;
} else if (arr[mid] > num) {
right = mid;
} else if (mode == "left") {
if (arr[mid - 1] != num) {
console.log("left bound:", mid);
return mid;
}
right = mid;
} else if (mode == "right") {
if (arr[mid + 1] != num) {
console.log("right bound:", mid);
return mid;
}
left = mid;
}
}
}
function countNum(arr, num) {
if (arr[0] == arr[arr.length - 1]) {
return arr.length;
} else if (arr.length == 2 && (arr[0] == num || arr[1] == num)) {
return 1;
} else if (arr.length == 2 && [0] != num && arr[1] != num) {
return -1;
} else {
return findBou(arr, num, "right") - findBou(arr, num, "left") + 1;
}
}
arr = [1, 1, 1, 1];
console.log(countNum(arr, 3));
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
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