1

次の配列があるとします。| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |

上記の配列を、右側がすべて 1、左側が 0 になるように並べ替える必要があります。

私は C++ で 2 つのアルゴリズムを考え出しました。

1つ目:

for(i = 0; i < n; i++) {
    if(a[i] == 1 && i != n - 1) {
        for(j = i + 1; j < n; j++) {
            if(a[j] == 0) {
                temp = a[j];
                a[i] = a[j];
                a[j] = temp;
                break;
            }
        }
    }
}

2つ目:

int x = 0;
for(i = 0; i < n; i++) {
    if(a[i] == 1) {
        for(j = n-x-1; j >= 0; j--) {
            if(a[j] == 0) {
                temp = a[j];
                a[i] = a[j];
                a[j] = temp;
                x++;
                break;
            }
        }
    if(x > n / 2)
    break;
}

両方の時間計算量を教えてください。また、どちらがより優れたパフォーマンスを発揮するかについても、説明付きのより優れたアルゴリズムを提案してくれます。ありがとう。

4

3 に答える 3

15

lengthOfArray - sum1 の数を数えてから、最初の要素を 0 で、次に 1 で配列を補充するだけです。複雑さは O(n) になります。

どちらの場合も、複雑さは O(n²) です

于 2013-10-01T08:38:40.610 に答える
3

@Alexandruが言ったように、それは良いことであり、 O(N) を与えるので、2回繰り返すだけです

  1. 0、1のカウントを見つけるには
  2. カウントが言うように、配列を1、0で埋めます。

別の代替 sort を探している場合は、 O(N) であるこれを見ることができます。

for(int i=0, j=n-1;i<j;)
{
if(a[i]==1 && a[j]==0) swap(a[i],a[j]);
else if(a[i]==1 && a[j]==1) j--;
else if(a[i]==0 && a[j]==0) i++;
else if(a[i]==0 && a[j]==1) {j--; i++;}
}
于 2013-10-01T09:09:47.420 に答える