本文介绍了一种在 O(max(log n, k)) 时间复杂度内，判断一个大小为 k 的已排序子数组是否存在于一个大小为 n 的已排序数组中的方法。该方法基于二分查找定位子数组的起始元素，并进行后续验证，尤其适用于 n 远大于 k 的情况。
问题描述
给定两个已排序的数组 v (大小为 n) 和 v’ (大小为 k，其中 k <= n)，目标是确定 v' 是否作为连续子数组存在于 v 中。例如，v = [-10, -3, 0, 4, 7, 19, 33] 和 v' = [4, 7, 19]，则应该返回 True。
解决方案
该问题的核心在于利用已排序数组的特性，结合二分查找和线性验证，将时间复杂度控制在 O(max(log n, k))。
算法步骤
二分查找起始元素： 在较大的数组 v 中，使用二分查找算法查找子数组 v’ 的第一个元素。二分查找的时间复杂度为 O(log n)。
线性验证： 如果在 v 中找到了 v’ 的第一个元素，则从该位置开始，线性地比较 v 和 v’ 的剩余元素。需要注意的是，这里假设 v’ 中的元素必须在 v 中连续存在。线性验证的时间复杂度为 O(k)。
序列猴子开放平台
具有长序列、多模态、单模型、大数据等特点的超大规模语言模型
0 查看详情
Python 代码示例
def is_subarray_present(v, v_prime): """ 检查排序子数组 v_prime 是否存在于更大的排序数组 v 中。 Args: v: 大的排序数组。 v_prime: 需要检查的排序子数组。 Returns: 如果 v_prime 存在于 v 中，则返回 True，否则返回 False。 """ n = len(v) k = len(v_prime) if k > n: return False # 二分查找 v_prime 的第一个元素 left, right = 0, n - 1 first_element_index = -1 while left <= right: mid = (left + right) // 2 if v[mid] == v_prime[0]: first_element_index = mid break # 找到第一个元素，退出循环 elif v[mid] = n or v[first_element_index + i] != v_prime[i]: return False return True# 示例v = [-10, -3, 0, 4, 7, 19, 33]v_prime = [4, 7, 19]result = is_subarray_present(v, v_prime)print(f"v_prime 是否存在于 v 中: {result}") # 输出: v_prime 是否存在于 v 中: Truev_prime2 = [4, 7, 20]result2 = is_subarray_present(v, v_prime2)print(f"v_prime2 是否存在于 v 中: {result2}") # 输出: v_prime2 是否存在于 v 中: Falsev_prime3 = [-10]result3 = is_subarray_present(v, v_prime3)print(f"v_prime3 是否存在于 v 中: {result3}") # 输出: v_prime3 是否存在于 v 中: Truev_prime4 = [33,34]result4 = is_subarray_present(v, v_prime4)print(f"v_prime4 是否存在于 v 中: {result4}") # 输出: v_prime4 是否存在于 v 中: False
时间复杂度分析
二分查找：O(log n)线性验证：O(k)
总时间复杂度：O(log n + k)。由于通常情况下我们关注的是最坏情况，可以将其表示为 O(max(log n, k))。 当 n 远大于 k 时，时间复杂度接近 O(log n)。
注意事项
该算法要求两个数组都已排序。线性验证部分假设子数组 v’ 在 v 中是连续的。如果允许 v’ 中的元素在 v 中不连续出现，则需要修改线性验证部分。如果 v_prime 为空数组，根据实际需求，可以返回 True 或 False。上述代码返回 True。
总结
通过结合二分查找和线性验证，我们可以在 O(max(log n, k)) 的时间复杂度内，有效地判断一个排序子数组是否存在于一个更大的排序数组中。这种方法在处理大型数据集时，可以显著提高效率。
以上就是检查排序子数组是否存在于更大的排序数组中：O(log n) 复杂度实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/337645.html
微信扫一扫 
支付宝扫一扫 
