在两个不同大小的数组中查找公共元素
我有一个问题是在两个数组中找到不同大小的公共元素。
取大小为n数组A1和大小为m数组A2 ， m != n
到目前为止，我已经尝试逐个迭代列表并将元素复制到另一个列表。 如果元素已经包含标记，但我知道它不是一个好的解决方案。
对数组进行排序。 然后用两个指针迭代它们，总是推进指向较小值的指针。 当他们指向相等的值时，您就有一个共同的价值。 这将是O（n + m），其中n和m是两个列表的大小。 它就像合并排序中的合并 ，但是当指向的值相等时，您只生成输出。
def common_elements(a, b): a.sort() b.sort() i, j = 0, 0 common = [] while i < len(a) and j < len(b): if a[i] == b[j]: common.append(a[i]) i += 1 j += 1 elif a[i] < b[j]: i += 1 else: j += 1 return common print 'Common values:', ', '.join(map(str, common_elements([1, 2, 4, 8], [1, 4, 9])))
输出
Common values: 1, 4
如果元素不具有可比性，则将一个列表中的元素抛出到散列映射中，并根据散列映射检查第二个列表中的元素。
如果你想提高效率，我会将较小的数组转换为hashset，然后迭代较大的数组并检查当前元素是否包含在hashset中。 与排序数组相比，散列函数是有效的。 排序数组很昂贵。
这是我的示例代码
import java.util.*; public class CountTest { public static void main(String... args) { Integer[] array1 = {9, 4, 6, 2, 10, 10}; Integer[] array2 = {14, 3, 6, 9, 10, 15, 17, 9}; Set hashSet = new HashSet(Arrays.asList(array1)); Set commonElements = new HashSet(); for (int i = 0; i < array2.length; i++) { if (hashSet.contains(array2[i])) { commonElements.add(array2[i]); } } System.out.println("Common elements " + commonElements); } }
输出：
共同元素[6,9,10]
在APL中：
∪A1∩A2
例：
A1←9, 4, 6, 2, 10, 10 A1 9 4 6 2 10 10 A2←14, 3, 6, 9, 10, 15, 17, 9 A2 14 3 6 9 10 15 17 9 A1∩A2 9 6 10 10 ∪A1∩A2 9 6 10
看起来像嵌套循环：
commons = empty for each element a1 in A1 for each element a2 in A2 if a1 == a2 commons.add(a1)
如果arrays具有相同的大小，Schould根本不重要。
根据所使用的语言和框架，设置操作可能会派上用场。
尝试堆叠两个数组，然后合并以查找交集。
Java示例：
public static >List intersection(Collection c1, Collection c2) { List result = new ArrayList (); PriorityQueue q1 = new PriorityQueue (c1), q2 = new PriorityQueue (c2); while (! (q1.isEmpty() || q2.isEmpty())) { E e1 = q1.peek(), e2 = q2.peek(); int c = e1.compareTo(e2); if (c == 0) result.add(e1); if (c <= 0) q1.remove(); if (c >= 0) q2.remove(); } return result; }
有关合并的更多示例，请参阅此问题 。
我给出的复杂性是O(N*M + N) 。
还要注意它是Pseudocode C并且它提供了不同的值。
例如。 [1,1,1,2,2,4]和[1,1,1,2,2,2,5]将返回[1,2]
复杂性是for循环的N*M原因
+ N引起检查它是否已存在于ArrayCommon[] （如果Array2[]包含复制Array1[]部分的数据，则为n大小。假设N是较小数组的大小（N
int Array1[m] = { Whatever }; int Array2[n] = { Whatever }; int ArrayCommon[n] = { }; void AddToCommon(int data) { //How many commons we got so far? static int pos = 0; bool found = false; for(int i = 0 ; i <= pos ; i++) { //Already found it? if(ArrayCommon[i] == data) { found = true; } } if(!found) { //Add it ArrayCommon[pos] = data; pos++; } } for(int i = 0 ; i < m ; i++) { for(int j = 0 ; j < n ; j++) { //Found a Common Element! if(Array1[i] == Array2[j]) AddToCommon(Array1[i]); } }
在Python中，您可以编写set(A1).intersection(A2) 。 这是最佳的O（n + m）。
你的问题虽然含糊不清。 A1 = [0,0]，A2 = [0,0,0]的结果是什么？ 对你的问题有合理的解释，在最终arrays中给出1,2,3或6个结果 – 你的情况需要什么？
我通过使用Set intersection解决了这个问题。 它非常优雅。 尽管我没有分析时间复杂度，但它可能在合理的范围内。
public Set FindCommonElements(Integer[] first, Integer[] second) { Set set1=new HashSet (Arrays.asList(first)); Set set2=new HashSet (Arrays.asList(second)); // finds intersecting elements in two sets set1.retainAll(set2); return set1; }
class SortedArr def findCommon(a,b) j =0 i =0 l1=a.length l2=b.length if(l1 > l2) len=l1 else len=l2 end while i < len if a[i].to_i > b[j].to_i j +=1 elsif a[i].to_i < b[j].to_i i +=1 else puts a[i] # OR store it in other ds i +=1 j +=1 end end end end t = SortedArr.new t.findCommon([1,2,3,4,6,9,11,15],[1,2,3,4,5,12,15])