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

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(n)时间内没有O(1)空间方法来查找两个未排序集的交集.

对于具有无限范围的数据类型,最小排序价格为O(n ln n).

对于具有有限范围基数排序的数据类型,可以在O(n ln n'n")时间内进行就地基数排序,其中n是数据的大小,n'是值的数量可以表示,并且n"与检查两个值是否在同一基数组中的成本有关.对于O(恩恩)空间价格,可以降低n"时间价格.

在32位整数的特殊情况下,n'是2 ^ 32且n"是1,因此这将崩溃为O(n)并为数十亿个记录集提供成功的解决方案.

对于无限大小的整数,n'和n"通过基数排除O(n)时间解.