15

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

给定 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) 时，我有点交替使用它们。没有额外的空间，我的意思是小的占位符变量很好，但分配新数组不是。

4

4 回答 4

7

没有 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) 时间解。

于 2012-11-08T21:33:09.540 回答
2

关键是对两个数组进行就地排序。我搜索了“就地基数排序”，并找到了就地基数排序。我相信这个问题是可以解决的，至少对于 Java int[]，通过应用这些想法对每个数组进行排序，一点一点地进行排序，然后进行明显的扫描。

顺便说一句，我认为问题代码中问题的正确输出是 1、2、3。

这是我的实现，基于对引用问题的回答：

    public class ArrayMatch {
      public static void main(String[] args) {
        int[] a = { 4, 1, 2, 3, 4 };
        int[] b = { 2, 5, 6, 7, 3, 2, 2, 2, 2, 1, 2, 2, 2, 2 };
        System.out.print("Original problem");
        printMatches(a, b);
        System.out.println();

        int[] a1 = { 4, 1, -1234, 2, 3, 4, Integer.MIN_VALUE };
        int[] b1 = { -1234, 2, 5, 6, 7, 3, 2, 2, 2, 2, 1, 2, 2, 2, 2 , Integer.MIN_VALUE, Integer.MAX_VALUE};
        System.out.print("With negatives");
        printMatches(a1, b1);
        System.out.println();

      }

      // Print all matching elements between the two arrays.
      private static void printMatches(int[] a, int[] b) {
        if (a.length == 0 || b.length == 0) {
          return;
        }

        sort(a);
        sort(b);

        int i = 0;
        int j = 0;
        while (true) {
          while (a[i] < b[j]) {
            i++;
            if (i == a.length) {
              return;
            }
          }
          while (a[i] > b[j]) {
            j++;
            if (j == b.length) {
              return;
            }
          }

          if (a[i] == b[j]) {
            System.out.print(" " + a[i]);

            do {
              i++;
            } while (i < a.length && a[i - 1] == a[i]);

            do {
              j++;
            } while (j < b.length && b[j - 1] == b[j]);
          }

          if (i == a.length || j == b.length) {
            return;
          }
        }
      }

      // In place radix sort.
      private static void sort(int[] in) {
        // Flip the sign bit to regularize the sort order
        flipBit(in, 31);
        sort(in, 0, in.length, 31);
        // Flip back the sign bit back to restore 2's complement
        flipBit(in, 31);
      }

      /**
       * Sort a subarray, elements start through end-1 of in, according to the
       * values in firstBit through 0.
       * 
       * @param in
       * @param start
       * @param end
       * @param firstBit
       */
      private static void sort(int[] in, int start, int end, int firstBit) {
        if (start == end) {
          return;
        }
        int mask = 1 << firstBit;
        int zeroCount = 0;
        for (int i = start; i < end; i++) {
          if ((in[i] & mask) == 0) {
            zeroCount++;
          }
        }

        int elements = end - start;
        int nextZeroIndex = start;
        int nextOneIndex = start + zeroCount;

        int split = nextOneIndex;

        if (zeroCount > 0 && zeroCount < elements) {
          while (nextZeroIndex < split) {
            if ((in[nextZeroIndex] & mask) != 0) {
              // Found a one bit in the zero area, look for its partner in the one
              // area
              while ((in[nextOneIndex] & mask) != 0) {
                nextOneIndex++;
              }
              int temp = in[nextZeroIndex];
              in[nextZeroIndex] = in[nextOneIndex];
              in[nextOneIndex] = temp;
              nextOneIndex++;
            }
            nextZeroIndex++;
          }

        }

        if (firstBit > 0) {
          sort(in, start, split, firstBit - 1);
          sort(in, split, end, firstBit - 1);
        }

      }

      private static void flipBit(int[] in, int bitNo) {
        int mask = 1 << bitNo;
        for (int i = 0; i < in.length; i++) {
          in[i] ^= mask;
        }
      }
    }
于 2012-11-08T23:25:29.937 回答
1

一个可能的答案类似于HashMap解决方案......如果您知道整数在一个非常小的窗口内。这将类似于：http ://en.wikipedia.org/wiki/Bucket_sort

基本上，如果保证整数在某个恒定大小的窗口内（即它们都是 1-1000），那么您可以通过递增索引的每个单元格在恒定空间中执行此操作 = 无论您的数字是多少。这与解决方案完全相同HashMap，只是您不需要像罐子那样考虑所有可能的整数HashMap，这样可以节省空间。如果不清楚，请在评论中告诉我，我会进一步解释。

于 2012-11-08T21:39:46.837 回答
0

我相信这可以通过额外的空间就地完成。我利用了数组中的元素既可变又可交换的附加假设，但我相信通过仔细考虑，可以针对这个特定问题删除可变性假设。O(1)

基本思想是进行就地散列。就地散列可以通过使用O(n) 中位数选择算法围绕一个合适的百分位数（例如第 90 个百分位数）划分数组来实现。这将阵列分为一小部分（约 10%）和大部分（约 90%），它们的元素可相互区分（小于或不小于分区元素）。然后，您可以通过交换从 10% 部分哈希到 90% 部分。此散列可用于检测重复项。这是O(n)每次处理 10% 的数组，所以做 10 次仍然是O(n). 我更详细地描述了这一点，尽管我打算在某一天在这个相关问题上更正一些手。.

对于这个特殊问题，您需要进行 3 次就地散列。首先在每个单独的数组上删除重复项。然后，在表示组合数组的包装器上（如果索引小于数组 1 的长度，则索引到数组 1，否则索引到数组 2）以报告重复项。

于 2012-11-08T22:42:19.773 回答