查找2排序阵列共同要素 [英] Find common elements in 2 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).

这篇关于查找2排序阵列共同要素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！