剑指offer-37、数字在升序数组中出现的次数
<h2 id="题目描述">题目描述</h2><p>统计⼀个数字在升序数组中出现的次数。</p>
<p>示例1<br>
输⼊：,3<br>
返回值：4</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="线性遍历">线性遍历</h3>
<p>顺序遍历数组，遇到目标值就计数</p>
<pre><code class="language-java">public class Solution {
public int GetNumberOfK(int[] array, int k) {
if (array == null || array.length == 0) {
return 0;
}
int count = 0;
for (int i = 0; i < array.length; i++) {
if (array == k) {
count++;
}
// 由于数组有序，如果当前元素已大于k，可提前结束
else if (array > k) {
break;
}
}
return count;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，最坏情况下需要遍历整个数组</li>
<li><strong>空间复杂度</strong>：O(1)，只使用常数级别额外空间</li>
</ul>
<h3 id="二分查找左右扫描法">二分查找+左右扫描法</h3>
<p>先使用二分查找定位到目标值，然后向两边扩展统计。</p>
<p>由于数组是有序的，可以明显看到是二分法。</p>
<p>第1步是找出数值为 k 的数的索引：<br>
假设数组为 nums[] ，⼀开始的左边索引为 left = 0 ，右边界索引为 right = nums.length-1</p>
<ol>
<li>将数组分成两部分，中间的数为 nums 。第1部分为 ,第2部分为。</li>
<li>如果 nums>k ,则说明 k 只可能存在前半部分中，对前半部分执⾏操作1。</li>
<li>如果 nums<k ,则说明 k 只可能存在后半部分中，对后半部分执⾏操作1。</li>
<li>如果 nums=k ,直接返回当前索引 mid 。</li>
<li>如果 left > right ,说明 k 不存在，则返回 -1 。</li>
</ol>
<p>找到索引之后，往两边扩展，同时统计k的个数，直到元素不等于 k 的时候停⽌。</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201707501.png" alt="" loading="lazy"></p>
<pre><code class="language-java">public class Solution {
public int GetNumberOfK(int[] array, int k) {
if (array == null || array.length == 0) return 0;
int left = 0, right = array.length - 1;
int count = 0;
// 二分查找
while (left <= right) {
int mid = left + (right - left) / 2;
if (array < k) {
left = mid + 1;
} else if (array > k) {
right = mid - 1;
} else {
// 找到目标值，向左右扩展统计
count = 1;
int temp = mid;
// 向左统计
while (--temp >= left && array == k) {
count++;
}
// 向右统计
temp = mid;
while (++temp <= right && array == k) {
count++;
}
break;
}
}
return count;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(log n + k)，其中k是目标值出现次数。当目标值出现次数较少时效率接近O(log n)，但最坏情况（全部是目标值）退化为O(n)</li>
<li><strong>空间复杂度</strong>：O(1)</li>
</ul>
<h3 id="双二分查找法推荐">双二分查找法（推荐）</h3>
<p>分别使用二分查找找到目标值的起始和结束位置，计算区间长度，这是最优解法。</p>
<pre><code class="language-java">public class Solution {
public int GetNumberOfK(int[] array, int k) {
if (array == null || array.length == 0) return 0;
// 找到第一个k的位置
int firstIndex = findFirstPosition(array, k);
// 找到最后一个k的位置
int lastIndex = findLastPosition(array, k);
if (firstIndex == -1 || lastIndex == -1) {
return 0; // 目标值不存在
}
return lastIndex - firstIndex + 1;
}
/**
* 查找目标值的第一个出现位置
*/
private int findFirstPosition(int[] array, int k) {
int left = 0, right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array < k) {
left = mid + 1;
} else if (array > k) {
right = mid - 1;
} else {
// 关键：检查是否为第一个出现位置
if (mid == 0 || array != k) {
return mid;
} else {
right = mid - 1; // 继续在左半部分查找
}
}
}
return -1; // 未找到
}
/**
* 查找目标值的最后一个出现位置
*/
private int findLastPosition(int[] array, int k) {
int left = 0, right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array < k) {
left = mid + 1;
} else if (array > k) {
right = mid - 1;
} else {
// 关键：检查是否为最后一个出现位置
if (mid == array.length - 1 || array != k) {
return mid;
} else {
left = mid + 1; // 继续在右半部分查找
}
}
}
return -1; // 未找到
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(log n)，执行两次二分查找</li>
<li><strong>空间复杂度</strong>：O(1)，只使用常数空间</li>
</ul>
<h3 id="k05边界查找法">k±0.5边界查找法</h3>
<p>一种巧妙的解法，通过查找目标值边界的插入位置来计算出现次数。</p>
<p>由于数组元素都是整数，k-0.5和k+0.5正好是目标值范围的边界，它们的插入位置差值就是目标值出现次数</p>
<pre><code class="language-java">public class Solution {
public int GetNumberOfK(int[] array, int k) {
if (array == null || array.length == 0) return 0;
// 查找k+0.5的插入位置（第一个大于k的位置）
int upperBound = findInsertPosition(array, k + 0.5);
// 查找k-0.5的插入位置（第一个大于等于k的位置）
int lowerBound = findInsertPosition(array, k - 0.5);
return upperBound - lowerBound;
}
/**
* 在有序数组中查找目标值的插入位置
*/
private int findInsertPosition(int[] array, double target) {
int left = 0, right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left; // 返回插入位置
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(log n)，两次二分查找</li>
<li><strong>空间复杂度</strong>：O(1)</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19204019
頁:
[1]