检查排序子数组是否存在于更大的排序数组中：O(log n) 复杂度实现-java教程-PHP中文网

检查排序子数组是否存在于更大的排序数组中：O(log n) 复杂度实现

DDD

发布： 2025-08-07 20:16:01

原创

414人浏览过

检查排序子数组是否存在于更大的排序数组中：o(log n) 复杂度实现

本文介绍了一种在 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)。

AutoGLM沉思
智谱AI推出的具备深度研究和自主执行能力的AI智能体

129

查看详情

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] < v_prime[0]:
            left = mid + 1
        else:
            right = mid - 1

    # 如果没有找到 v_prime 的第一个元素，则 v_prime 不存在于 v 中
    if first_element_index == -1:
        return False

    # 线性验证剩余元素
    for i in range(1, k):
        if first_element_index + i >= 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 中: True

v_prime2 = [4, 7, 20]
result2 = is_subarray_present(v, v_prime2)
print(f"v_prime2 是否存在于 v 中: {result2}") # 输出: v_prime2 是否存在于 v 中: False

v_prime3 = [-10]
result3 = is_subarray_present(v, v_prime3)
print(f"v_prime3 是否存在于 v 中: {result3}") # 输出: v_prime3 是否存在于 v 中: True

v_prime4 = [33,34]
result4 = is_subarray_present(v, v_prime4)
print(f"v_prime4 是否存在于 v 中: {result4}") # 输出: v_prime4 是否存在于 v 中: False

登录后复制

时间复杂度分析