当前位置：首页 > news >正文

图解LeetCode——剑指 Offer 53 - I. 在排序数组中查找数字 I

news 2025/6/27 18:27:36

一、题目

统计一个数字在排序数组中出现的次数。

二、示例

示例 1

【输入】nums = [5,7,7,8,8,10], target = 8
【输出】2

示例 2:

【输入】nums = [5,7,7,8,8,10], target = 6
【输出】0

提示：

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个 非递减 数组
-10^9 <= target <= 10^9

三、解题思路

首先，根据题目描述，我们可以得知题目给我们的数组nums是一个有序的数组，那么针对这个特性我们可以得出结论，即：相同的数字会紧密的排列在一起。所以，根据这个结论，我们可以采用双指针来解决这个问题，步骤如下所示：

【步骤1】通过头指针head，从数组的第一个元素开始向后遍历对比，如果发现nums[head]等于target，则停止遍历。
【步骤2】通过尾指针tail，从数组的最后一个元素开始向前遍历对比，如果发现nums[tail]等于target，则停止遍历。
【步骤3】最后，通过 tail - head + 1 计算，就可以统计一个数字在排序数组中出现的次数。

解题思路如上所述，那么我们以入参: nums = [5,7,7,8,8,10], target = 8为例，演示一下具体的处理流程，请见下图所示：

四、代码实现

class Solution {public int search(int[] nums, int target) {int head = 0, tail = nums.length - 1;while (head < nums.length && nums[head] < target) head++;while (tail >= 0 && nums[tail] > target) tail--;return (head > tail) ? 0 : (tail - head + 1);}
}