如何在 O(n) 中找到两个排序数组的所有匹配项

Question

不仅仅是合并连接可以解决，就像标题一样，我有两个数组，每个数组包含n个元素，并且已经从最小到最大排序，我想找到两个数组之间的所有匹配项，即相邻元素数组 A 可能对应于数组 B 的相同元素。但是，我有一个限制，即我只能将 A 数组的每个元素与 B 数组的元素进行 ceil(log(n)) 次比较，这仅够一次二分查找.

为了比较元素，有一个函数运行在 O(1) 中，告诉函数 A 和 B 中的元素，如果匹配则返回，较高或较低。所以我们不能简单地合并连接两个数组。

我怎样才能在 O(n) 时间内完成这个任务。

我尝试过以下方法

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

2. 选取A的中间元素，在B中二分查找，然后根据B中的结果将B数组分成两部分，如果不考虑最坏情况，则总体时间复杂度如果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;
    }