在两个数组中搜索匹配项，没有额外的内存

Question

前几天，我接受了亚马逊的采访，他们问我一个问题，涉及以下问题。

给定2个整数数组，其中包含任意数量的正负元素，请查找出现在两个数组中的数字。

我能够非常轻松地解决此问题，HashMaps因此它将具有O(n)计算复杂性，但是不幸的是，这还将具有O(n)空间复杂性。可以通过遍历每个数组中的所有元素而无需额外的内存来完成此操作，但这将是O(n^2)。

在我解释完该HashMap方法之后，面试官问我是否可以想到一种在计算上为O（n）但不会使用任何额外内存的方法。我想不出任何动态，也无法为此找到解决方案。有没有一种方法可以在线性时间内不使用额外的内存来查找这些值？

注意：我已经在CareerCup上发布了这个问题，但是那里的每个人似乎都没有得到这样的概念，即我不需要使用它来占用额外的空间，并且必须在O(n)计算上使用它。

这是我在面试中使用的代码。它可以工作，但是空间不是O（1）。

import java.util.*;
public class ArrayFun {
    public static void main(String[] args) {

        int[] a = {1,2,3,4};
        int[] b = {2,5,6,7,3,2,2,2,2,1,2,2,2,2};
        ArrayList<Integer> matches = ArrayFun.findMatches(a,b);
        for (int i = 0;i<matches.size();++i) {
            System.out.println(matches.get(i));
        }
    }

    public static ArrayList<Integer> findMatches(int[] a, int[] b) {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        ArrayList<Integer> matches = new ArrayList<Integer>();
        for (int i = 0;i<a.length;++i) {
            map.put(a[i],0);
        }
        for (int i = 0;i<b.length;++i) {
            if (map.get(b[i]) != null && map.get(b[i]) == 0) {
                map.put(b[i],1);
                matches.add(b[i]);
            }
        }
        return matches;
    }
}

此代码将返回

1,2,3

编辑：同样，当我说没有额外的空间和O（1）时，我有点可以互换使用它们。没有多余的空间，我是说较小的占位符变量很好，但分配新数组则不行。

Answer 1

没有O（1）空间方法可以找到O（n）时间中两个未排序集合的交集。

对于无限范围的数据类型，最小排序价格为O（n ln n）。

对于范围有限的数据类型，基数排序提供了在O（n ln
n’n“）时间中进行就地基数排序的能力，其中n是数据的大小，n’是值的数量可以表示，n“与检查两个值是否在同一基数组中的开销有关。可以降低n“时间价格，以换取O（ln
n）空间价格。

在32位整数的特殊情况下，n’为2 ^ 32，n“为1，因此这将折叠为O（n）并为数十亿个记录集提供一个成功的解决方案。

对于大小不受限制的整数，n’和n“排除通过基数的O（n）时间解。