1

给定两个整数数组，如何有效地找出这两个数组是否有共同的元素？

有人能想出比这更好的空间复杂度吗（我也希望在程序中指出错误，谢谢！！）。

是否可以使用 XOR 来解决这个问题？

public boolean findcommon(int[] arr1, int[] arr2) {
  Set<int> s = new Hashset<int>();
  for(int i=0;i<arr1.length;i++) {
    if(!s.contains(arr1[i]))
      s.add(arr1[i]);
  }
  for(int i=0;i<arr2.length;i++) {
    if(s.contains(arr2[i]))
        return true;
  }
  return false;
}
4

4 回答 4

2

由于您要求更节省空间的解决方案：

当您接受 O(n log n) 的运行时间并允许更改数组时，您可以对它们进行排序，然后进行线性传递以查找公共元素。

于 2013-01-27T09:37:02.397 回答
1

鉴于您的解决方案仅尝试查找两个数组中是否存在一个元素，以下是将为您执行此操作的代码：

 public boolean findCommon(int[] arr1, int[] arr2) {
      HashTable hash = new HashTable();
      for (item : arr1){
         if !(hash.containsKey(item)){
            hash.put(item, "foo");
         }
      }
      for (item : arr2){
         if (hash.containsKey(item)){
           return(true);
         }
      }
      return(false);
 }

对于两个不共享单个元素的数组，这仍然具有 O(n) 的最坏情况复杂度。如果正如您最初的问题所建议的那样，您担心的是空间复杂性（例如，如果您不必存储 HashTable，您会很乐意接受性能下降），您可以按照这些思路去做：

    public boolean findCommon(int[] arr1, int[] arr2){
        for (item : arr1){
           for(item2 : arr2){
               if(item ==item2){
                   return(true);
               }
           }
        }
        return(false);
    }

这将解决您的空间复杂性问题，但会具有 O(n^2) 的（客观上可怕的）时间复杂性。

如果您要在其周围放置更多参数，这可以简化（假设您碰巧知道至少有一个数组已排序，或者更好的是，两者都已排序）。

但是在您问的通配符示例中，我相信它确实会归结为 O(n) 与空间复杂度的哈希表，或者空间复杂度较低的 O(n^2)。

于 2013-01-27T09:32:40.777 回答
1

如果你只需要做一次，那么你不能做得比时间复杂度 O(n+m) 更好，其中 n 和 m 是数组的各自长度。您必须遍历两个数组中的输入，别无选择（否则您将如何查看所有输入？），因此仅输入处理就会具有这种复杂性，没有必要做一些更有效的事情。如果您需要随着数组的增长继续搜索，那就另当别论了。

因此，您建议的实施方式的问题归结为“包含”需要多长时间？由于您使用的是 Hashset，因此 contains 是常数时间 O(1)，因此您需要 O(n) 来创建哈希集和 O(m) 来验证第二个数组中的元素。放在一起，O（n + m）。够好了 ;）

如果您正在寻找改进的空间复杂度，您首先需要能够对原始数组进行更改。但我认为没有任何方法可以使用比 O(n) 更少的额外空间并且仍然在 O(n+m) 时间内执行。

注意：我不确定你在想什么异或。如果您正在考虑按位或逻辑 XOR，那么这里没有用。如果您正在考虑 Set XOR，那么它在逻辑上是否有用并不重要，因为它不在 Java Sets 的实现中，所以您仍然必须自己动手。

于 2013-01-27T09:28:43.770 回答
0

您可以使用 O(n*m) 阶算法来改善空间占用（这是问题对吗？）。只需获取每一对元素并比较它们......这在时间上很糟糕，但不使用任何额外的内存。否则，您可以就地对两个数组进行排序（如果您被允许修改它们）并在 O(max(n,m)) 中找到公共元素。

于 2013-01-27T09:38:34.067 回答