当前位置: 首页> 财经> 创投人物 > 重庆百度seo代理_国家市场监督管理总局副局长_互联网整合营销推广_搜易网服务内容

重庆百度seo代理_国家市场监督管理总局副局长_互联网整合营销推广_搜易网服务内容

时间:2025/7/11 10:28:08来源:https://blog.csdn.net/apple_67445472/article/details/143196112 浏览次数:0次
重庆百度seo代理_国家市场监督管理总局副局长_互联网整合营销推广_搜易网服务内容

在这里插入图片描述

img

😀前言
在编程中,查找有序数组中特定元素的出现次数是一个常见的问题。本文将详细讲解这个问题的解决方案,并通过二分查找法优化效率。

🏠个人主页:尘觉主页

文章目录

  • 🥰数字在排序数组中出现的次数
    • 💖题目链接
    • 💗题目描述
      • 示例
    • 💞解题思路
      • 寻找第一个出现位置
      • 寻找最后一个出现位置
    • 😊代码实现
      • 二分查找:查找第一个 `K`
      • 计算 `K` 的出现次数
    • 💝代码解释
      • 边界情况
      • 示例解析
    • 🥰时间复杂度分析
    • 😄总结

🥰数字在排序数组中出现的次数

💖题目链接

牛客网

💗题目描述

给定一个递增排序的数组 nums 和一个目标数字 K,要求找到该数字在数组中出现的次数。例如,输入数组 nums = [1, 2, 3, 3, 3, 3, 4, 6],目标数字 K = 3,输出为 4,因为数字 3 出现了 4 次。

示例

Input:
nums = 1, 2, 3, 3, 3, 3, 4, 6
K = 3Output:
4

💞解题思路

我们可以利用数组的有序性,通过二分查找的方式来优化查找过程。具体思路是:

  1. 找到目标数字 K 第一次出现在数组中的位置。
  2. 找到目标数字 K 最后一次出现在数组中的位置。
  3. 利用两次查找到的索引,计算出该数字出现的次数。

寻找第一个出现位置

为了找到 K 第一次出现在数组中的位置,我们可以对标准二分查找进行修改:

  • nums[mid] == K 时,不能立即返回,而应该继续向左边(低索引)搜索,以找到 K 出现的最早位置。
  • 如果 nums[mid] >= K,则搜索左区间(即缩小 high),否则继续搜索右区间。

寻找最后一个出现位置

类似地,我们可以寻找 K 最后一次出现的位置。或者,我们可以通过查找 K + 1 第一次出现的位置,再向前移动一位得到 K 最后一次出现的位置。

通过查找 K 的第一个和 K + 1 的第一个位置,两个索引的差就是 K 在数组中的出现次数。

😊代码实现

二分查找:查找第一个 K

private int binarySearch(int[] nums, int K) {// 初始化 low 为数组的起始索引 0,high 为数组的长度(即 nums.length)int low = 0, high = nums.length;// 使用 while 循环,当 low 小于 high 时继续迭代while (low < high) {// 计算 mid,mid 是 low 和 high 的中间索引,防止溢出的写法int mid = low + (high - low) / 2;// 如果 nums[mid] 大于等于 K,则将 high 设为 mid// 意思是当前的 mid 可能是我们要找的元素位置,但还需要继续检查更前面的部分if (nums[mid] >= K) {high = mid;} else {// 否则,说明 mid 处的元素小于 K,应该向右侧查找low = mid + 1;}}// 当 low == high 时,low 即为第一个大于等于 K 的元素的索引return low;
}

计算 K 的出现次数

通过上面的 binarySearch 函数,可以进一步计算 K 出现的次数:

public int GetNumberOfK(int[] nums, int K) {int first = binarySearch(nums, K);  // 找到 K 第一次出现的位置int last = binarySearch(nums, K + 1);  // 找到 K+1 第一次出现的位置// 如果 K 不在数组中,直接返回 0return (first == nums.length || nums[first] != K) ? 0 : last - first;
}
  1. 首先通过 binarySearch(nums, K) 查找到 K 第一次出现的位置。
  2. 然后通过 binarySearch(nums, K + 1) 查找到大于 K 的第一个数字的位置。
  3. 通过 last - first 计算 K 的出现次数。如果 first 超出了数组的范围,或者 nums[first] != K,则说明数组中没有 K,返回 0

💝代码解释

  1. binarySearch(nums, K) 用于查找 K 第一次出现的位置。在找到 K 之后,继续搜索左半部分,直到确定其第一次出现的位置。
  2. binarySearch(nums, K + 1) 用于查找比 K 大的第一个元素的位置,进而通过该位置计算出 K 的最后一次出现的位置。
  3. 最终的 GetNumberOfK 方法结合了这两个查找结果,返回 K 在数组中出现的次数。

边界情况

  • 如果数组为空,返回 0。
  • 如果数组中没有 K,返回 0。
  • 如果 K 在数组中的出现次数为 1 或多次,程序也能正确处理。

示例解析

考虑以下数组:

nums = [1, 2, 3, 3, 3, 3, 4, 6]
K = 3
  1. binarySearch(nums, 3) 找到 3 第一次出现的位置,即索引 2。
  2. binarySearch(nums, 4) 找到第一个比 3 大的元素(即 4)的位置,即索引 6。
  3. 因此,3 出现的次数为 6 - 2 = 4

🥰时间复杂度分析

  • 时间复杂度: 由于每次查找的时间复杂度是 O(log n),因此两次二分查找的总时间复杂度为 O(log n)。
  • 空间复杂度: 只使用了常数空间,空间复杂度为 O(1)。

😄总结

通过二分查找的方式,可以在 O(log n) 的时间复杂度下高效地计算有序数组中某个数字的出现次数。这种方法不仅适用于该特定问题,还可以应用于其他类似的查找问题,如查找有序数组中的区间或范围。掌握二分查找的变形技巧,对于解决数组相关问题非常有帮助。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞

img

关键字:重庆百度seo代理_国家市场监督管理总局副局长_互联网整合营销推广_搜易网服务内容

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: