53. 在排序数组中查找数字 I
53. 在排序数组中查找数字 I
题目
某班级考试成绩按非严格递增顺序记录于整数数组 scores,请返回目标成绩 target 的出现次数。
示例 1:
输入: scores = [2, 2, 3, 4, 4, 4, 5, 6, 6, 8], target = 4
输出: 3
示例 2:
输入: scores = [1, 2, 3, 5, 7, 9], target = 6
输出: 0
提示:
0 <= scores.length <= 10^5
-10^9 <= scores[i] <= 10^9
scores
是一个非递减数组-10^9 <= target <= 10^9
注意
本题与 LeetCode 第 34 题 相同。
解题思路
这道题可以使用二分查找来解决。由于题目中给出的数组 scores
是非递减的,我们可以使用二分查找来找到目标成绩 target
在数组中的起始位置和结束位置,然后计算出现次数。具体步骤如下:
- 初始化两个指针
left
和right
分别指向数组的起始位置和结束位置。 - 使用二分查找找到目标成绩
target
在数组中的起始位置,更新指针left
。 - 使用二分查找找到目标成绩
target
在数组中的结束位置,更新指针right
。 - 计算目标成绩
target
在数组中的出现次数,即right - left + 1
。 - 返回计算得到的出现次数。
代码
/**
* @param {number[]} scores
* @param {number} target
* @return {number}
*/
var countTarget = function (scores, target) {
const binarySearch = (arr, isLeft) => {
let left = 0;
let right = arr.length - 1;
let res = -1;
while (left <= right) {
let mid = Math.floor((right - left) / 2) + left;
if (arr[mid] == target) {
res = mid;
if (isLeft) {
right = mid - 1; // 继续往左边找
} else {
left = mid + 1; // 继续往右边找
}
} else if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return res;
};
const leftIndex = binarySearch(scores, true);
const rightIndex = binarySearch(scores, false);
// 目标成绩不存在
if (leftIndex == -1 || rightIndex == -1) {
return 0;
}
return rightIndex - leftIndex + 1;
};