java - 搜索两个数组进行匹配，没有额外的内存

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) 时间解决方案。