C语言 在两个不同大小的数组中查找公共元素

Finding common elements in two arrays of different size

提问by Jijoy

I have a problem to find common elements in two arrays and that's of different size.

我在寻找两个数组中的公共元素时遇到了问题，而且它们的大小不同。

Take , Array A1of size nand Array A2of size m, and m != n

Take , Array A1of sizen和 Array A2of size m，和m != n

So far, I've tried to iterate lists one by one and copy elements to another list. If the element already contains mark it, but I know it's not a good solution.

到目前为止，我已经尝试一个一个地迭代列表并将元素复制到另一个列表。如果元素已经包含标记它，但我知道这不是一个好的解决方案。

回答by moinudin

Sort the arrays. Then iterate through them with two pointers, always advancing the one pointing to the smaller value. When they point to equal values, you have a common value. This will be O(n+m) where n and m are the sizes of the two lists. It's just like a merge in merge sort, but where you only produce output when the values being pointed to are equal.

对数组进行排序。然后用两个指针遍历它们，始终将指向较小值的指针前进。当它们指向相等的值时，您就有了一个共同的值。这将是 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])))

outputs

产出

Common values: 1, 4

If the elements aren't comparable, throw the elements from one list into a hashmap and check the elements in the second list against the hashmap.

如果元素不具有可比性，则将一个列表中的元素放入哈希图中，并根据哈希图检查第二个列表中的元素。

回答by Jacorb Effect

If you want to make it efficient I would convert the smaller array into a hashset and then iterate the larger array and check whether the current element was contained in the hashset. The hash function is efficient compared to sorting arrays. Sorting arrays is expensive.

如果您想让它高效，我会将较小的数组转换为哈希集，然后迭代较大的数组并检查当前元素是否包含在哈希集中。与排序数组相比，散列函数是有效的。排序数组很昂贵。

Here's my sample code

这是我的示例代码

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);
    }    
}

Output:

输出：

Common elements [6, 9, 10]

常见元素 [6, 9, 10]

回答by StackPC

In APL:

在 APL 中：

∪A1∩A2

example:

例子：

      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 

回答by V.Reeve

Throw your A2 array into a HashSet, then iterate through A1; if the current element is in the set, it's a common element. This takes O(m + n) time and O(min(m, n)) space.

将你的 A2 数组放入一个 HashSet，然后遍历 A1；如果当前元素在集合中，则它是一个公共元素。这需要 O(m + n) 时间和 O(min(m, n)) 空间。

回答by Eiko

Looks like nested loops:

看起来像嵌套循环：

commons = empty
for each element a1 in A1
   for each element a2 in A2
      if a1 == a2
         commons.add(a1)

Schouldn't matter at all if the arrays have the same size.

如果数组具有相同的大小，则根本无关紧要。

Depending on the language and framework used, set operations might come in handy.

根据所使用的语言和框架，集合操作可能会派上用场。

回答by finnw

Try heapifyingboth arrays followed by a merge to find the intersection.

尝试堆化两个数组，然后进行合并以找到交集。

Java example:

Java示例：

public static <E extends Comparable<E>>List<E> intersection(Collection<E> c1,
                                                            Collection<E> c2) {
    List<E> result = new ArrayList<E>();
    PriorityQueue<E> q1 = new PriorityQueue<E>(c1),
                     q2 = new PriorityQueue<E>(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;
}

See this questionfor more examples of merging.

有关合并的更多示例，请参阅此问题。

回答by finnw

The Complexity of what I give is O(N*M + N).

我给出的复杂性是O(N*M + N).

Also note that it is PseudocodeC And that it provides distinct values.

另请注意，它是PseudocodeC 并且它提供了不同的值。

eg.[1,1,1,2,2,4]and [1,1,1,2,2,2,5]Will return [1,2]

例如。[1,1,1,2,2,4]并且[1,1,1,2,2,2,5]会回来[1,2]

The Complexity is N*Mcause of the forloops

复杂性是 循环的N*M原因for

+ Ncause of the checking if it already exists in the ArrayCommon[](which is nsize in case Array2[]contains data which duplicate Part of the Array1[]Assuming N is the size of the smaller Array (N < M).

+ N检查它是否已经存在的原因ArrayCommon[]（这是n大小，以防Array2[]包含重复的数据Array1[]假设 N 的一部分是较小数组的大小（N < M）。

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]);
    }
}

回答by finnw

In Python, you would write set(A1).intersection(A2). This is the optimal O(n + m).

在 Python 中，您将编写set(A1).intersection(A2). 这是最优的 O(n + m)。

There's ambiguity in your question though. What's the result of A1=[0, 0], A2=[0, 0, 0]? There's reasonable interpretations of your question that give 1, 2, 3, or 6 results in the final array - which does your situation require?

不过你的问题有歧义。A1=[0, 0], A2=[0, 0, 0] 的结果是什么？对您的问题有合理的解释，在最终数组中给出 1、2、3 或 6 个结果 - 您的情况需要哪个？

回答by alan turing

I solve the problem by using Set intersection. It is very elegant. Even though I did not analyze the time complexity, it is probably in reasonable range.

我通过使用设置交集解决了这个问题。它非常优雅。虽然我没有分析时间复杂度，但应该在合理范围内。

public Set FindCommonElements(Integer[] first, Integer[] second)
{

    Set<Integer> set1=new HashSet<Integer>(Arrays.asList(first));
    Set<Integer> set2=new HashSet<Integer>(Arrays.asList(second));

    // finds intersecting elements in two sets
    set1.retainAll(set2);

    return set1;

}

回答by user2476720

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])