在两个排序的数组中查找共同的元素 [英] Find common elements in two sorted arrays

问题描述

可能重复:
两个排序数组的交集

我们有两个排序的数组A和B，除了将一个数组与其他数组中的所有元素进行比较之外，如何设计最佳算法来查找具有其公共元素的数组?

We have two sorted arrays A and B, besides compare one with all the elements in other array, how to design a best algorithm to find the array with their common elements?

推荐答案

按住两个指针:每个数组一个.

Hold two pointers: one for each array.

i <- 0, j <- 0
repeat while i < length(arr1) and j < length(arr2):
    if arr1[i] > arr2[j]: increase j
    else if arr1[i] < arr2[j]: increase i
    else : output arr[i], increase both pointers

想法是，如果对数据进行排序，则如果元素在一个数组中太大"，那么对数组中剩余的所有其他元素来说，它都将太大"，因为已对其进行了排序.

The idea is, if the data is sorted, if the element is "too big" in one array, it will be "too big" for all other elements left in the array - since it is sorted.

此解决方案需要对数据进行一次遍历. O(n)(也具有良好的常数).

This solution requires a single traversal on the data. O(n) (with good constants as well).

这篇关于在两个排序的数组中查找共同的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！