c - 查找两个数组中每个索引处不匹配的元素

Question

假设我下面有两个数组(相同长度)，该数组未排序(随机):

a[] = {1, 3, 5, 7, 10, 11}
b[] = {1, 4, 5, 7, 9, 11}

我可以知道查找这两个数组之间所有不匹配(不同)值的最快方法是什么吗？ (索引信息就足够了)。非常感谢您抽出时间。

Answer 1

如果您只对数组 a 和 b 中具有不同值的单元格对应的索引感兴趣，只需迭代两个数组并检查它们的索引是否相等就足够了。下面给出的参数N表示数组a和b的大小。

int get_unmatched_indices(int a[], int b[], int N, int indices[])
{
    int i, num_unmatched = 0;
    for(i = 0; i < n; ++i)
    {
        if (a[i] != b[i])
        {
            indices[num_unmatched++] = i;
        }
    }
    return num_unmatched;
}

上面的函数使用O(N)额外空间(对于索引)和O(N)时间来查找您要查找的信息。如果您随后想要打印找到的索引处不匹配的元素，则可以迭代索引并打印每个 a[indices[X]] 和 b[indices[X]] 的值。

是否可以实现更高效率的说明:

任何依赖于比较 a 和 b 中元素值的方法都需要读取 a 和 b 中的每个元素。通过反证法证明这一点是微不足道的。假设您可以跳过比较索引 i 处的 a[i] 和 b[i] 的值。那么，你就无法知道a[i]和b[i]是否是不匹配的元素，因为跳过了一个不可或缺的信息。

现在，在某些问题类别中存在一些比基于比较的算法更好的方法。排序就是一个例子。有一些基于比较的排序算法，其最多为 O(NlogN)，但也有其他算法具有 O(N) 复杂度，并具有其他某些限制。因此，从理论上讲，似乎有某种非基于比较的方法可以发挥作用。然而，即使在这些算法中，您至少需要处理所有基本信息。 (即遍历每个元素并将其处理为某种形式)因此即使如此，您也已经达到了 O(N) 复杂性。因此，您可能设计的任何算法充其量都可以提供恒定的效率系数。