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

一、题目

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

二、示例

示例 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为例，演示一下具体的处理流程，请见下图所示：

四、代码实现

classSolution {
publicintsearch(int[] nums, inttarget) {
inthead=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);
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」