如何在 O(n) 时间内找到两个已排序数组的所有匹配项，并且限制比较次数？

Question

我有两个数组。每个包含 n 个元素。它们按升序排列。我想找到两个数组之间的所有匹配项。数组 A 中的两个相邻元素可能对应于数组 B 中的相同元素。

有两个限制：

1. 算法的时间复杂度应为 O(n)

2. 我只能将 A 中的每个元素与 B 中的值进行有限次数的比较：最多 ceil(log(n)) 次。这意味着 A 中的每个值最多可以执行一次二分搜索。

要比较元素，我需要使用运行时间复杂度为 O(1) 的

compare

函数。该函数可以有三个不同的返回值：

1. 如果两个给定值匹配，或者
2. 第一个小于第二个，或者
3. 第一个大于第二个。

所以我们不能简单地合并两个数组。

如何在 O(n) 时间内完成这个任务？

我尝试过以下方法：

1. 比较这两个数组的每个元素从头到尾。但是，如果 A 的所有元素都与 B 的最后一个元素匹配，我们将超出 ceil(log(n)) 的比较时间限制。

2. 选取A的中间元素，在B中进行二分查找，然后将B数组分成2个分区。如果不考虑最坏的情况，总体时间复杂度由下式决定：

   T(n) = 2T(n/2) + logn, ...没关系。然而，在最坏的情况下，A的所有元素都对应B中的最小或最大元素，那么时间复杂度由

   决定

   T(n) = 2T(n/2) + logm, ...这不是 O(n)。

我没有其他想法了。如何在给定的约束下设计该算法？或者也许我计算时间复杂度的方式有误？

Answer 1

public static List<Integer> findMatchedElements(int[] arr1, int[] arr2) {
        List<Integer> matchedElements= new ArrayList<>();
        int i = 0; // Pointer for arr1
        int j = 0; // Pointer for arr2
        
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] == arr2[j]) {
                matchedElements.add(arr1[i]);
                i++;
                j++;
            } else if (arr1[i] < arr2[j]) {
                i++;
            } else {
                j++;
            }
        }
        
        return matchedElements;
    }

Answer 2

public static List<Integer> findMatchedElements(int[] arr1, int[] arr2) {
    List<Integer> matchedElements = new ArrayList<>();
    int i = 0; // Pointer for arr1
    int j = 0; // Pointer for arr2

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] == arr2[j]) {
            matchedElements.add(arr1[i]);
            i++;
            j++;
        } else if (arr1[i] < arr2[j]) {
            i++;
        } else {
            // Use binary search to find the next greater or equal element in arr2
            int searchResult = binarySearch(arr2, arr1[i], j, arr2.length - 1);
            if (searchResult != -1) {
                j = searchResult;
            } else {
                break; // No need to continue, no more matches possible
            }
        }
    }

    return matchedElements;
}

private static int binarySearch(int[] arr2, int target, int left, int right) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr2[mid] == target) {
            return mid;
        } else if (arr2[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    // If no exact match found, return the index of the next greater element
    if (left < arr2.length) {
        return left;
    }
    return -1; // No greater or equal element found
}