在两个数组中搜索匹配项，无需额外内存

arrays algorithm java

2022-09-03 15:32:07

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

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

我能够非常容易地解决这个问题，因此它具有计算复杂性，但不幸的是，这也将具有空间复杂性。这可以通过循环访问每个数组中的所有元素来完成，而无需额外的内存，但这是。HashMapsO(n)O(n)O(n^2)

面试官在我解释完方法后，问我是否可以想到一种在计算上是O（n）的方法，但不会使用任何额外的内存。我无法在飞行中想到任何东西，并且无法找到解决方案。有没有办法在线性时间中不使用额外的内存来查找这些值？HashMap

注意：我已经在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）时，我有点互换使用它们。通过没有额外的空间，我的意思是小占位符变量很好，但分配新数组不是。

答案 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）时间解。

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