搜索两个数组的比赛中，没有任何额外的内存 [英] Searching two arrays for matches, no extra memory

问题描述

我有一次采访那天与亚马逊和问题，他们问我是属于下面的问题。

I had an interview the other day with Amazon, and a question they asked me was pertaining to the following problem.

由于2的整数数组，包含任意数量的元素正面和负面的，发现出现在两个数组号。

Given 2 integer arrays, containing any number of elements both positive and negative, find numbers that appear in both arrays.

我能解决这个问题很容易与 HashMaps这样所以它必须 O（N）计算复杂性，但不幸的是这也将有 O（N）空间复杂度。这可能没有额外的内存，通过每个阵列中的所有元素进行迭代来完成，但是这将是为O（n ^ 2）。

I was able to solve this problem very easily with HashMaps so it would have O(n) computational complexity, but unfortunately this will also have O(n) space complexity. This could be done with no extra memory by iterating through all elements in each array, but this would be O(n^2).

在面试后，我完成了解释的HashMap 的方法，问我能不能想到一个方法，这将是为O（n）计算的，但不会使用任何额外的记忆。我想不出任何的飞行，并没有能够找到一个解决方案。有没有使用额外的内存，以线性的时间找到这些值的方法是什么？

The interviewer, after I finished explaining the HashMap method, asked if I could think of a method that would be O(n) computationally, but would not use any extra memory. I could not think of any on the fly, and have not been able to find a solution for this. Is there a way of finding these values without using extra memory, in linear time?

注：我已经张贴在CareerCup这个问题，但每个人都在那里似乎没有得到我需要它不使用额外的空间的概念，而且它必须是 O（N） 计算。

Note: I have posted this question on CareerCup, but everyone on there does not seem to get the concept that I need it to not use extra space, and that it has to be O(n) computationally.

下面是code在面试过程中我使用。它的工作原理，但仅仅是不O（1）空间。

Here is the code I used during the interview. It works, but just is not O(1) for space.

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

这code将返回

1,2,3

编辑：还当我说没有额外的空间和O（1），我使用一种他们可以互换。通过没有额外的空间，我的意思是小的占位符变量都不错，但分配新的数组是没有的。

also when I say no additional space, and O(1), I am kind of using them interchangeably. By no additional space I mean small placeholder variables are fine but allocating new arrays is not.

推荐答案

有没有O（1）找出两个未排序集合的交集在O（n）时间空间的方法。

There is no O(1) space method for finding the intersection of two unsorted sets in O(n) time.

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

For a data type with an unlimited range, the minimum sorting price is O(n ln n).

对于一个有限的范围内基数排序的数据类型提供了做一个就地基数排序为O能力（N LN N'N）的时间，其中n为数据的大小，N'是数字可重新presented，和n个值的，是因为有检查两个值是否相同基数组中的成本。第n的时候价格可以换取一个O（LN n）的空间，价格被丢弃。

For a data type with a limited range radix sort provides the ability to do an in-place radix sort in O(n ln n' n") time, where n is the size of the data, n' is the number of values that can be represented, and n" has to do with the cost of checking whether two values are in the same radix group. The n" time price can be dropped in return for an O(ln n) space price.

在32位整数的特殊情况下，n'为2 ^ 32和n是1，所以这会崩溃到O（n）和提供的数十亿记录集一个成功的解决方案。

In the special case of 32-bit integers, n' is 2^32 and n" is 1, so this would collapse to O(n) and provide a winning solution for multi-billion record sets.

有关无限大的整数，N和经基数N preclude一个O（n）时间的解决方案。

For integers of unlimited size, n' and n" preclude an O(n) time solution via radix.

这篇关于搜索两个数组的比赛中，没有任何额外的内存的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！