algorithm - 找出两个数组共有的最大元素？

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

Answer 3

虽然这取决于特定语言中各种操作的时间复杂度，但如何从数组创建集合并在两个集合的交集处找到最大值呢？根据 Python 中操作的时间复杂度，平均而言，集合分配为 O(n)，交叉点为 O(n)，找到最大值为 O(n)。所以平均情况是O(n)。

然而！最坏情况是 O(len(a) * len(b)) -> O(n^2)，因为集合交点的最坏情况时间复杂度。

更多信息在这里，如果你有兴趣：http ://wiki.python.org/moin/TimeComplexity

Answer 4

如果您已经知道数组中的数字范围，则可以执行计数排序，然后执行所需的二进制搜索。这将产生 O(n) 运行时。

Answer 5

伪代码：

sort list1 in descending order
sort list2 in descending order
item *p1 = list1
item *p2 = list2
while ((*p1 != *p2) && (haven't hit the end of either list))
  if (*p1 > *p2)
    ++p1;
  else
    ++p2;
// here, either we have *p1 == *p2, or we hit the end of one of the lists
if (*p1 == *p2)
  return *p1;
return NOT_FOUND;

Answer 6

不是一个完美的，而是一个简单的解决方案，O(len(array1) + len(array2))

import sys


def find_max_in_common(array1, array2):
    array1 = set(array1)
    array2 = set(array2)

    item_lookup = {}

    for item in array1:
        item_lookup[item] = True

    max_item = -sys.maxsize

    intersection = False

    for item in array2:
        if not item_lookup.get(item, None):
            continue
        else:
            intersection = True
            if item > max_item:
                max_item = item

    return None if not intersection else max_item