7

サイズがNのN個の配列があり、それらがすべてソートされている場合、余分なスペースを使用できない場合、どのようにしてそれらの共通データを効率的に、または時間の複雑さを抑えて見つけることができますか？

例：

 1. 10 160 200 500 500
 2. 4 150 160 170 500
 3. 2 160 200 202 203
 4. 3 150 155 160 300
 5. 3 150 155 160 301

これはインタビューの質問です。似たような質問がいくつか見つかりましたが、入力が並べ替えられたり、追加のメモリを使用できないという追加の条件が含まれていませんでした。

O（n ^ 2 lg n）の複雑さよりも小さい解決策は考えられませんでした。その場合、私はこの複雑さを私に与える最も単純な解決策を選びたいと思います。それは次のとおりです。

  not_found_flag = false

  for each element 'v' in row-1
       for each row 'i' in the remaining set
           perform binary search for 'v' in 'i'
           if 'v' not found in row 'i'
                 not_found_flag = true
                 break
       if not not_found_flag 
           print element 'v' as it is one of the common element

各行の最小値と最大値を比較し、それに基づいて、数値「num」がその行の「min_num」と「max_num」の間に入る可能性があるかどうかを判断することで、これを改善できます。

二分探索->O（log n）n-1行の1 numを検索する場合：O（nlogn）最初の行の各数値の二分探索：O（n2logn）

最初の行を選択しました。任意の行を選択できます。選択した行の要素が（N-1）行のいずれにも見つからない場合、実際には共通のデータがありません。

4

5 に答える 5

7

これはO(n^2);で実行できるようです。つまり、各要素を 1 回見るだけです。要素がすべての配列に共通である場合、その要素はそれらのいずれかに存在する必要があることに注意してください。また、説明のために (上記の for ループを使用したため)、各配列のインデックスを保持できると仮定しますが、これを回避する方法については後で説明します。

A_1を介して配列を呼び出し、1 から始まるインデックスを使用しましょうA_N。疑似コード:

# Initial index values set to first element of each array
for i = 1 to N:
  x_i = 1 

for x_1 = 1 to N:
  val = A_1[x_1] 
  print_val = true
  for i = 2 to N:
    while A_i[x_i] < val:
      x_i = x_i + 1
    if A_i[x_i] != val:
      print_val = false
  if print_val:
    print val

アルゴリズムの説明。最初の配列 (または任意の配列) を参照アルゴリズムとして使用し、他のすべての配列を並行して反復処理します (N 個の配列を除いて、マージ ソートのマージ ステップのようなものです)。すべての配列に共通であり、他のすべての配列に存在する必要があります。したがって、他の配列ごとに (それらはソートされているため)、x_iそのインデックスの値が少なくとも探している値になるまでインデックスを増やしA_i[x_i]ます (より小さい値は気にしません。それらは共通ではありません)。配列がソートされているため、単調に非減少であるため、これを行うことができます。すべての配列がこの値を持っている場合は、それを出力します。そうでない場合はx_1、参照配列をインクリメントして続行します。値を出力しない場合でも、これを行う必要があります。

最後に、すべての配列に共通するすべての値を出力しましたが、各要素は 1 回だけ調べました。

追加のストレージ要件を回避する。これを行うには多くの方法がありますが、最も簡単な方法は、各配列の最初の要素を確認し、最大値を参照配列として取得することだと思いますA_1。それらがすべて同じである場合は、その値を出力し、インデックスx_2 ... x_Nを各配列自体の最初の要素として格納します。

入力例を使用したJava実装（簡潔にするため、余分なハックなし）：

public static void main(String[] args) {
    int[][] a = {
            { 10, 160, 200, 500, 500, },
            { 4, 150, 160, 170, 500, },
            { 2, 160, 200, 202, 203, },
            { 3, 150, 155, 160, 300 },
            { 3, 150, 155, 160, 301 } };

    int n = a.length;
    int[] x = new int[n];

    for( ; x[0] < n; x[0]++ ) {
        int val = a[0][x[0]]; 
        boolean print = true;
        for( int i = 1; i < n; i++ ) {
            while (a[i][x[i]] < val && x[i] < n-1) x[i]++;              
            if (a[i][x[i]] != val) print = false;               
        }   
        if (print) System.out.println(val);
    }   
}

出力：

160
于 2013-02-23T04:30:59.953 に答える
2

これは python の解決策であり、O(n^2)余分なスペースを使用しませんが、リストを破棄します:

def find_common(lists):
    num_lists = len(lists)
    first_list = lists[0]
    for j in first_list[::-1]:
        common_found = True
        for i in range(1,num_lists):
            curr_list = lists[i]
            while curr_list[len(curr_list)-1] > j:
                curr_list.pop()
            if curr_list[len(curr_list)-1] != j:
                common_found = False
                break
        if common_found:
            return j
于 2013-03-27T06:29:29.007 に答える
1

追加のストレージを使用しないが、元の配列を変更するO（n ^ 2）（Python）バージョン。共通の要素を印刷せずに保存できます。

data = [
    [10, 160, 200, 500, 500],
    [4, 150, 160, 170, 500],
    [2, 160, 200, 202, 203],
    [3, 150, 155, 160, 300],
    [3, 150, 155, 160, 301],
]

for k in xrange(len(data)-1):
    A, B = data[k], data[k+1]
    i, j, x = 0, 0, None

    while i<len(A) or j<len(B):
        while i<len(A) and (j>=len(B) or A[i] < B[j]):
            A[i] = x
            i += 1

        while j<len(B) and (i>=len(A) or B[j] < A[i]):
            B[j] = x
            j += 1

        if i<len(A) and j<len(B):
            x = A[i]
            i += 1
            j += 1

print data[-1]

私がやっていることは、基本的にデータ内のすべての配列を取得し、次の配列と要素ごとに比較して、一般的でない配列を削除することです。

于 2013-02-24T01:14:20.467 に答える
1

ここにJavaの実装があります

public static Integer[] commonElementsInNSortedArrays(int[][] arrays) {
    int baseIndex = 0, currentIndex = 0, totalMatchFound= 0;
    int[] indices = new int[arrays.length - 1];
    boolean smallestArrayTraversed = false;
    List<Integer> result = new ArrayList<Integer>();
    while (!smallestArrayTraversed && baseIndex < arrays[0].length) {
        totalMatchFound = 0;
        for (int array = 1; array < arrays.length; array++) {
            currentIndex = indices[array - 1];
            while (currentIndex < arrays[array].length && arrays[array][currentIndex] < arrays[0][baseIndex]) {
                currentIndex ++;                    
            }

            if (currentIndex < arrays[array].length) {
                if (arrays[array][currentIndex] == arrays[0][baseIndex]) {
                    totalMatchFound++;
                }
            } else {
                smallestArrayTraversed = true;
            }
            indices[array - 1] = currentIndex;
        }
        if (totalMatchFound == arrays.length - 1) {
            result.add(arrays[0][baseIndex]);
        }
        baseIndex++;
    }

    return result.toArray(new Integer[0]);
}

ここに単体テストがあります

@Test
public void commonElementsInNSortedArrayTest() {
    int arr[][] = { {1, 5, 10, 20, 40, 80},
                    {6, 7, 20, 80, 100},
                    {3, 4, 15, 20, 30, 70, 80, 120}
                   };

    Integer result[] = ArrayUtils.commonElementsInNSortedArrays(arr);
    assertThat(result, equalTo(new Integer[]{20, 80}));

    arr = new int[][]{
            {23, 34, 67, 89, 123, 566, 1000},
            {11, 22, 23, 24,33, 37, 185, 566, 987, 1223, 1234},
            {23, 43, 67, 98, 566, 678},
            {1, 4, 5, 23, 34, 76, 87, 132, 566, 665},
            {1, 2, 3, 23, 24, 344, 566}
          };

    result = ArrayUtils.commonElementsInNSortedArrays(arr);
    assertThat(result, equalTo(new Integer[]{23, 566}));
}
于 2016-03-06T06:25:30.577 に答える