剑指Offer系列(java版,详细解析)53.在排序数组中查找数字
程序员文章站
2023-12-28 12:04:40
...
题目描述
剑指 Offer 53 - I. 在排序数组中查找数字 I
难度简单119收藏分享切换为英文接收动态反馈
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
限制:
0 <= 数组长度 <= 50000
**注意:**本题与主站 34 题相同(仅返回值不同):https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
测试用例
- 功能测试(数组中包含要查找的数字;数组中没有要查找的数字;要查找的数字在数组中出现一次/多次)
- 边界值测试(查找数组中的最大值、最小值;数组中只有一个数字)
- 特殊输入测试(表示数组的指针为空指针)
题目考点
- 考察应聘者的只是迁移能力。
- 考察应聘者对二分查找算法的理解程度。
解题思路
一看到在排序数组中查找,大家一定能想到二分查找法,但是怎么用可以减少复杂度,that is problem.
- 利用二分查找法找出最早(左)出现的k的下标
- 利用二分查找法找出最晚(右)出现的k的下标
class Solution {
public int search(int[] nums, int target) {
// 搜索右边界 right
int i = 0, j = nums.length - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] <= target) i = m + 1;
else j = m - 1;
}
int right = i;
// 若数组中无 target ,则提前返回
if(j >= 0 && nums[j] != target) return 0;
// 搜索左边界 right
i = 0; j = nums.length - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] < target) i = m + 1;
else j = m - 1;
}
int left = j;
return right - left - 1;
}
}