15

先日、Amazon のインタビューを受けましたが、次の問題に関する質問がありました。

任意の数の正と負の要素を含む 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（n）時間で2つのソートされていないセットの共通部分を見つけるためのO（1）空間法はありません。

範囲が無制限のデータ型の場合、最小ソート価格はO（n ln n）です。

範囲が制限されたデータ型の場合、基数ソートは、O（n ln n'n "）時間でインプレース基数ソートを実行する機能を提供します。ここで、nはデータのサイズ、n'は次の値の数です。を表すことができ、n"は2つの値が同じ基数グループにあるかどうかをチェックするコストと関係があります。n "の時間価格は、O（ln n）スペース価格と引き換えに下げることができます。

32ビット整数の特殊なケースでは、n'は2^ 32、n "は1であるため、これはO（n）に崩壊し、数十億のレコードセットに最適なソリューションを提供します。

サイズが無制限の整数の場合、n'およびn"は、基数によるO（n）時間の解を排除します。

于 2012-11-08T21:33:09.540 に答える
2

重要なのは、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

考えられる答えの 1 つは、ソリューションに似ていHashMapます...整数が非常に小さなウィンドウ内にあることがわかっている場合。これは次のようになります: http://en.wikipedia.org/wiki/Bucket_sort

基本的に、整数が特定の一定サイズのウィンドウ内にあることが保証されている場合 (つまり、それらはすべて 1-1000 です)、 index = の各セルをインクリメントすることで、一定のスペースでそれを行うことができます。これはソリューションとまったく同じHashMapですが、can のように可能なすべての整数を考慮する必要がない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 に答える