3

入力配列のサブシーケンスである配列を返すライブラリ関数に配列を渡しています。つまり、1 番目と 2 番目の配列の順序は同じですが、2 番目の配列には 1 番目の配列の要素がいくつ欠けていてもかまいません。どちらの配列にも重複はありません!

次に、入力にはあったが関数の出力には含まれていないすべての要素の新しい配列を作成したいと思います。

些細なことのように聞こえますが、何らかの理由で、特に配列の最後で間違っているようです。

例 1 (典型的):

入力配列 a:

[ yyz, ltn, tse, uln, ist, gva, doh, hhn, vlc, ios, app, tlv, lcy ]

入力配列 b:

[ yyz, ltn, tse, uln, ist, gva, doh, hhn, vlc, tlv, lcy ]

出力配列「差分」:

[ ios, app ]

例 2 (最小限、違いが文字列の最後にある場合にいくつかのバグが明らかになります):

入力配列 a:

[ usa ]

入力配列 b:

[ ]

出力配列「差分」:

[ usa ]

(JavaScript / jQuery で実装するつもりですが、実際にはオブジェクトの配列を扱うので、疑似コードの汎用アルゴリズムにもっと興味があります。 C/C++ のようなポインターより)

4

3 に答える 3

3

2 番目の配列bは同じ順序の最初の配列aのサブセットであるため、両方を並行して処理し、現在の値を比較して、現在の a の値がbの現在の値と異なる場合は、その値を取得できます。

var a = ['yyz','ltn','tse','uln','ist','gva','doh','hhn','vlc','ios','app','tlv','lcy'],
    b = ['yyz','ltn','tse','uln','ist','gva','doh','hhn','vlc','tlv','lcy'],
    diff = [];
var i=0, j=0, n=a.length, m=b.length;
while (i<n && j<m) {
    if (a[i] !== b[j]) {
        diff.push(a[i]);
    } else {
        j++;
    }
    i++;
}
while (i<n) {
    diff.push(a[i++]);
}

whileまたは、ループを 1 つだけにしたい場合は、次のようにします。

// …
while (i<n) {
    if (j<m && a[i] === b[j]) {
        j++;
    } else {
        diff.push(a[i]);
    }
    i++;
}
于 2011-12-29T09:40:03.413 に答える
0

Javaでは、配列を使用する必要がある場合、おそらくこのようなことをするでしょう。返されたすべてのオブジェクトをループする必要があり、それらを送信したすべてのオブジェクトと比較する必要があるため、最悪の場合、O(n^2) の複雑さがあると思いますが、おそらく可能です。送信したリストを並べ替え、ポインターを使用して各位置を確認することでこれを改善します (ただし、ポインターを使用したくないため、このサンプルは省略します)。これを O(n) で比較できる場合があります。

public void doYourJob(){
        Object[] allObjects = new Object[10]; //hold all original values
        Object[] recivedArray = yourBlackBox(allObjects); //send in the array an gets the smaller one
        Object[] missingArray = new Object[allObjects.length - recivedArray.length];
        for(Object inObj : allObjects){
            boolean foundObject = false;
            for(Object obj : recivedArray){
                if(inObj.equals(obj)){
                    foundObject = true;
                    break;
                }
            }
            if(!foundObject)
                missingArray add inObj //add the missing object. This is not correct java code. =)
        }
    }

Collection インターフェースから何かを声に出して使用すると、「myArray.contains()」メソッドを使用できるため、これははるかに簡単になります。

代わりにリストを使用

public void doYourJob(){
        List<Object> allObjects = new ArrayList<Object>(); //hold all original values
        List<Object>  recivedArray = yourBlackBox(allObjects); //send in the array an gets the smaller one
        List<Object>  missingArray = new ArrayList<Object>();
        for(Object inObj : allObjects){
            if(!recivedArray.contains(inObj))
                missingArray.add(inObj);
        }
    }
于 2011-12-29T09:28:16.257 に答える
0

配列に課される保証された順序はありますか? もしそうなら、次のようなことをするのは比較的簡単なはずです:

# our inputs are array1 and array2, array2 is the one with 0 or more missing elements
ix1 = 0
ix2 = 0
diff = new array
while ix2 < length(array2)
  while (ix1 < length(array1)) and (array1[ix1] != array2[ix2])
     add array1[ix1] to diff
     ix1 = ix1 + 1
  ix1 = ix1 + 1
  ix2 = ix2 + i

return diff

順序付けがない場合は、順序付けを行う (両方の配列を並べ替える) か、ハッシュ テーブルを使用できます。

hash = new hash
diff = new array

for each element in array1
  hash[element] = 1

for each element in array2
  hash[element] = hash[element] + 1

for each key in hash
  if hash[key] == 1
    add hash[key] to diff

配列への要素の追加が O(1) の場合 (その場合のみ)、これらは両方とも (大まかに) O(n) で実行する必要があります (結果の配列がいっぱいになるたびにサイズを 2 倍にする場合、少なくとも漸近的に O(1))。

于 2011-12-29T09:40:37.693 に答える