24

これは面接の質問です。swap配列から要素を削除し、同じ配列の後ろに追加することを意味します。整数の配列が与えられたら、swaps配列をソートするために必要な最小数を見つけます。

より良い解決策はありO(n^2)ますか？

例えば：

入力配列：[3124]。

数swaps：2（[3124]-> [1243]-> [1234]）。

4

15 に答える 15

24

問題は、入力配列にサブシーケンスとして表示される、ソートされた配列の最長のプレフィックスを見つけることに要約されます。これにより、並べ替える必要のない要素が決まります。残りの要素は、小さいものから大きいものへと1つずつ削除し、後ろに追加する必要があります。

あなたの例で[3, 1, 2, 4]は、すでにソートされているサブシーケンスは[1, 2]です。最適な解決策は、残りの2つの要素とを削除し、3それら4を後ろに追加することです。したがって、最適なソリューションは2つの「スワップ」です。

サブシーケンスの検索は、追加のメモリO(n logn)を使用して時間内に実行できます。O(n)次の擬似コードがそれを行います（コードはたまたま有効なPythonでもあります）：

l = [1, 2, 4, 3, 99, 98, 7]
s = sorted(l)
si = 0
for item in l:
  if item == s[si]:
    si += 1
print len(l) - si

あなたの例のように、配列にから1までの整数の順列が含まれている場合、メモリを使用して問題を時間n内に解決できます。O(n)O(1)

l = [1, 2, 3, 5, 4, 6]
s = 1
for item in l:
  if item == s:
    s += 1
print len(l) - s + 1

より一般的には、2番目の方法は、出力配列が事前にわかっている場合はいつでも使用できるため、並べ替えによって見つける必要はありません。

于 2012-11-25T08:42:50.563 に答える
8

これはO(nlogn)、連続した値の配列を想定していない場合でも機能する可能性があります。
もしそうなら - それはで行うことができますO(n)。それを行う1つの方法は、O(n)空間とO(nlogn)時間です。
指定された配列を 2 番目の配列にA並べ替えます ( O(nlogn)) B。
今... (配列は 1 からインデックス付けされます)

swaps = 0
b = 1
for a = 1 to len(A)
  if A[a] == B[b]
    b = b + 1
  else
    swaps = swaps + 1
于 2012-11-25T07:47:13.197 に答える
4

観察: 要素が後ろにスワップされた場合、その前の位置は問題になりません。要素を複数回交換する必要はありません。

観察: 最後のスワップ (ある場合) は、最大の要素を移動する必要があります。

観察: スワップの前に、配列 (最後の要素を除く) をソートする必要があります (以前のスワップによって、または最初に)

値が連続的であると仮定した並べ替えアルゴリズム: 1 から始まる連続した (値による) 要素の並べ替えられた最長の部分列を見つけます。

3 1 5 2 4

上位のすべての要素を順番に入れ替えます。

1 5 2 4 3

1 5 2 3 4

1 2 3 4 5

O(n)でスワップの数を見つけるには、1 から始まる連続した要素の最長の並べ替えられたサブシーケンスの長さを見つけます。

  • 期待値 = 1
  • 要素ごとに順番に
    • 要素 == 期待される場合
      • 期待値 += 1
  • リターン期待値-1

次に、スワップの数 = 入力の長さ - その最長のソートされたサブシーケンス。

入力が 1..n の順列でない場合の代替ソリューション( O(n^2) ):

  • スワップ = 0
  • ループ
    • 最大要素の最初のインスタンスを見つけ、配列がソートされているかどうかを検出します
    • 配列がソートされている場合は、スワップを返します。
    • それ以外の場合は、見つかった要素を配列から削除し、スワップを増やします。

一意の要素を想定したさらに別のソリューション( O(n log n) ):

  • 各要素を {oldPos, newPos, value} でラップします
  • 配列の浅いコピーを作成する
  • 配列を値でソートする
  • 各要素の新しい位置を保存する
  • (ソートされていない) コピーの newPos で順列のアルゴリズムを実行します

入力配列をコピーしたくない場合は、代わりに最後のステップの前に oldPos で並べ替えます。

于 2012-11-25T07:42:36.830 に答える
2

O(1) スペースと O(N) (~ 2*N) ソリューションは、最小要素が 1 で、配列に 1 から N-1 までのすべての数値が重複値なしで含まれていると仮定します。ここで、N は配列の長さです。

int minimumSwaps(int[] a) {
    int swaps = 0;
    int i = 0;
    while(i < a.length) {
        int position = a[i] - 1;
        if(position != i) {
            int temp = a[position];
            a[position] = a[i];
            a[i] = temp;
            swaps++;
        } else {
            i++;
        }
    }
    return swaps;
}
于 2019-06-22T07:08:01.003 に答える
1 
int numSwaps(int arr[], int length) {
bool sorted = false; 
int swaps = 0;
while(!sorted) {
    int inversions = 0;
    int t1pos,t2pos,t3pos,t4pos = 0;
    for (int i =  1;i < length; ++i)
    {
        if(arr[i] < arr[i-1]){
            if(inversions){
                tie(t3pos,t4pos) = make_tuple(i-1, i);
            }
            else tie(t1pos, t2pos) = make_tuple(i-1, i);
            inversions++;
        }
        if(inversions == 2)
            break;
    }
    if(!inversions){
        sorted = true;
    }
    else if(inversions == 1) {
        swaps++; 
        int temp = arr[t2pos];
        arr[t2pos] = arr[t1pos];
        arr[t1pos] = temp;
    }
    else{
        swaps++;
        if(arr[t4pos] < arr[t2pos]){
            int temp = arr[t1pos];
            arr[t1pos] = arr[t4pos];
            arr[t4pos] = temp;
        }
        else{
            int temp = arr[t2pos];
            arr[t2pos] = arr[t1pos];
            arr[t1pos] = temp;
        }
    }
}
return swaps;
}

このコードは、配列をインプレースでソートするために必要なスワップの最小数を返します。

たとえば、A[] = [7,3,4,1] 1 と 7 を交換すると、[1,3,4,7] が得られます。同様に、B[] = [1,2,6,4,8,7,9]. 最初に 6 を 4 と交換するので、B[] -> [1,2,4,6,8,7,9] になります。次に 7 と 8 です。つまり -> [1,2,4,6,7,8,9]

アルゴリズムは O(インデックス i の値 < インデックス i-1 の値のペアの数) ~ O(N) で実行されます。

于 2016-01-02T11:23:14.063 に答える
1 
for(int count = 1; count<=length; count++)
{
    tempSwap=0; //it will count swaps per iteration
    for(int i=0; i<length-1; i++)
        if(a[i]>a[i+1])
        {
           swap(a[i],a[i+1]);
           tempSwap++;
        }
    if(tempSwap!=0) //check if array is already sorted!
        swap += tempSwap;
    else
        break;
}
System.out.println(swaps);
于 2019-03-03T18:49:18.243 に答える
0

@all 、@Itay karo および @NPE によって提供される受け入れられたソリューションは、スワップされた要素の将来の順序を考慮していないため、完全に間違っています...

次のような多くのテストケースで失敗します。

3 1 2 5 4

正しい出力: 4

しかし、それらのコードは出力を3 ...

説明: 3 1 2 5 4--->1 2 5 4 3--->1 2 4 3 5--->1 2 3 5 4--->1 2 3 4 5

PS:評判が悪いのでコメントできません

于 2015-01-10T13:10:38.487 に答える