在两个排序数组中查找公共元素 [英] 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屋！