找到两个数组中常见的最大元素？

Question

给定两个数组,如何找到两个数组共有的最大元素？

我正在考虑对两个数组进行排序(n log n),然后对另一个数组中的一个排序数组(从较大的数组开始)中的每个元素执行二进制搜索,直到找到匹配为止.

例如:

a = [1,2,5,4,3]
b = [9,8,3]

Maximum common element in these array is 3

我们能比n log n做得更好吗？

Answer 1

使用一些额外的空间,您可以在1个数组中进行散列,然后在另一个数组的每个元素上执行包含,以跟踪返回true的最大值.是O(n).

Answer 2

你可以使用O(N)空间.
只需浏览第一个数组并将所有元素放在一个数组中HashTable.这是O(N)
然后通过第二个数组跟踪当前最大值并检查元素是否在HashTable.这也是O(N).所以总的运行时间O(N)和O(N)额外的空间HashTable

Java中的示例:

public static int getMaxCommon(int[] a, int[] b){  
  Set<Integer> firstArray = new HashSet<Integer>(Arrays.asList(a));  
  int currentMax = Integer.MIN_VALUE;  
  for(Integer n:b){  
     if(firstArray.contains(n)){  
         if(currentMax < n){  
              currentMax = n  
         }
     }   
  }   
  return currentMax;  
}