C++ 两个已排序数组的交集
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2400157/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
The intersection of two sorted arrays
提问by user288609
Given two sorted arrays: Aand B. The size of array Ais Laand the size of array Bis Lb. How to find the intersection of Aand B?
给定两个排序数组：A和B。阵列的大小A是La与阵列的大小B是Lb。如何找到的路口A和B？
If Lais much bigger than Lb, then will there be any difference for the intersection finding algorithm?
如果La比 大得多Lb，那么求交点算法会有什么不同吗？
采纳答案by amit
回答by codaddict
Since this looks like a HW...I'll give you the algorithm:
因为这看起来像一个硬件......我会给你算法：
Let arr1,arr2 be the two sorted arrays of length La and Lb.
Let i be index into the array arr1.
Let j be index into the array arr2.
Initialize i and j to 0.
while(i < La and j < Lb) do
if(arr1[i] == arr2[j]) { // found a common element.
print arr[i] // print it.
increment i // move on.
increment j
}
else if(arr1[i] > arr2[j])
increment j // don't change i, move j.
else
increment i // don't change j, move i.
end while
回答by Nazar
I've been struggling with same problem for a while now, so far I came with:
我一直在为同样的问题苦苦挣扎，到目前为止，我得到了：
Linear matching which will yield O(m+n) in worst case. You basically keep two pointers (A and B) each pointing to beginning of each array. Then advance pointer which points to smaller value, until you reach end of one of arrays, that would indicate no intersection. If at any point you have *A == *B - here comes your intersection.
Binary matching. Which yields ~ O(n*log(m)) in worst case. You basically pick smaller array and perform binary search in bigger array of all elements of the smaller array. If you want to be more fancy, you can even use last position where binary search failed and use it as starting point for next binary search. This way you marginally improve worst case but for some sets it might perform miracles :)
Double binary matching. It's a variation of regular binary matching. Basically you get element from the middle of smaller array and do binary search in bigger array. If you find nothing then you cut smaller array in half (and yes you can toss element you already used) and cut bigger array in half (use binary search failure point). And then repeat for each pair. Results are better than O(n*log(m)) but I am too lazy to calculate what they are.
在最坏情况下将产生 O(m+n) 的线性匹配。您基本上保留了两个指针（A 和 B），每个指针都指向每个数组的开头。然后前进指向较小值的指针，直到到达数组之一的末尾，这表示没有交集。如果在任何时候你有 *A == *B - 这就是你的交叉点。
二进制匹配。在最坏的情况下产生 ~ O(n*log(m)) 。您基本上选择较小的数组并在较小数组的所有元素的较大数组中执行二进制搜索。如果你想更花哨，你甚至可以使用最后一个二进制搜索失败的位置，并将其用作下一个二进制搜索的起点。通过这种方式，您可以略微改善最坏的情况，但对于某些系列，它可能会创造奇迹:)
双二进制匹配。它是常规二进制匹配的一种变体。基本上你从较小数组的中间获取元素并在较大数组中进行二分搜索。如果你什么也没找到，那么你将较小的数组切成两半（是的，你可以扔掉你已经使用过的元素）并将较大的数组切成两半（使用二进制搜索失败点）。然后对每一对重复。结果比 O(n*log(m)) 好，但我懒得计算它们是什么。
Those are two most basic ones. Both have merits. Linear is a bit easier to implement. Binary one is arguably faster (although there are plenty of cases when linear matching will outperform binary).
这是最基本的两个。两者各有千秋。线性更容易实现。二元匹配可以说更快（尽管在很多情况下线性匹配会优于二元匹配）。
If anyone knows anything better than that I would love to hear it. Matching arrays is what I do these days.
如果有人知道比这更好的事情，我很乐意听到。匹配数组是我这些天所做的。
P.S. don't quote me on terms "linear matching" and "binary matching" as I made them up myself and there are probably fancy name for it already.
PS 不要引用我的术语“线性匹配”和“二进制匹配”，因为它们是我自己编造的，而且可能已经有很花哨的名字了。
回答by Rajendra Uppal
void Intersect()
{
int la, lb;
la = 5;
lb = 100;
int A[5];
int i, j, k;
i = j = k = 0;
for (; i < 5; ++i)
A[i] = i + 1;
int B[100];
for (; j < 100; ++j)
B[j] = j + 2;
int newSize = la < lb ? la : lb;
int* C = new int[newSize];
i = j = 0;
for (; k < lb && i < la && j < lb; ++k)
{
if (A[i] < B[j])
i++;
else if (A[i] > B[j])
j++;
else
{
C[k] = A[i];
i++;
j++;
}
}
for (k = 0; k < newSize; ++k)
cout << C[k] << NEWLINE;
}
回答by Kushal Shinde
Let's consider two sorted arrays: -
让我们考虑两个排序数组：-
int[] array1 = {1,2,3,4,5,6,7,8};
int[] array2 = {2,4,8};
int i=0, j=0; //taken two pointers
While loop will run till both pointers reach up to the respective lengths.
While 循环将一直运行，直到两个指针都达到各自的长度。
while(i<array1.length || j<array2.length){
if(array1[i] > array2[j]) //if first array element is bigger then increment 2nd pointer
j++;
else if(array1[i] < array2[j]) // same checking for second array element
i++;
else { //if both are equal then print them and increment both pointers
System.out.print(a1[i]+ " ");
if(i==a1.length-1 ||j==a2.length-1) //one additional check for ArrayOutOfBoundsException
break;
else{
i++;
j++;
}
}
}
Output will be: -
输出将是： -
2 4 8
回答by Shiva
Very Simple with the PYTHON
使用 PYTHON 非常简单
Example:A=[1,2,3,5,7,9,90] B=[2,4,10,90]
示例：A=[1,2,3,5,7,9,90] B=[2,4,10,90]
Here we go three lines of code
下面我们来三行代码
for i in A:
if(i in B):
print(i)
Output:2, 90
输出：2, 90
回答by Kartik
//intersection of two arrays
#include<iostream>
using namespace std;
int main() {
int i=0,j=0,m,n;
int arr1[i],arr2[j];
cout<<"Enter the number of elements in array 1: ";
cin>> m;
cout<<"Enter the number of elements in array 2: ";
cin>>n;
for (i=0;i<m;i++){
cin>> arr1[i];
}
for(j=0;j<n;j++){
cin>> arr2[j];
}
for(j=0;j<n;j++){
for(i=0;i<m;i++) {
if (arr1[i] == arr2[j]){
cout<< arr1[i];
cout << ' ';
break;
}
}
}
return 0;
}
