3

配列をソートするコードを C# で書いています。右側にすべての負の値、左側にすべての正の値が必要です。降順であってはなりません。

namespace SortApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] newInt = new int[] { 5, -2, -1, -4, -20, 6, 7, -14, 15, -16, 8, 9, 10 };
            int size = 12, i= 0;             // or newInt.Length

            for (i = 0; i < newInt.Length; i++)
            {
                if (newInt[i] < 0 && newInt[size] > 0)
                {
                    int temp = newInt[i];
                    newInt[i] = newInt[size];
                    newInt[size] = temp;
                    size--;
                }
            }
            for (i = 0; i < newInt.Length; i++)
            {
                Console.Write(newInt[i]);
                Console.Write(" ");
            }
        }
    }
}

しかし、出力は次のようになります (-20 は間違った側にあります):

5 10 9 8 -20 6 7 -14 15 -16 -4 -1 -2

しかし、意図した出力は次のとおりです。

5 10 9 8 15 6 7 -14 -20 -16 -4 -1 -2

コードが意図した出力を生成しないのはなぜですか?

4

5 に答える 5

5

あなたのソリューションは、ループをいつ終了するかを誤って決定します。iまた、ループヘッダーで無条件にインクリメントしsize、負の数を指してもデクリメントしません。

これを修正する方法は次のとおりです。

for (i = 0; i < size ; ) {
    if (newInt[i] < 0 && newInt[size] >= 0) {
        int temp = newInt[i];
        newInt[i] = newInt[size];
        newInt[size] = temp;
        size--;
        i++;
        continue;
    }
    if (newInt[i] >= 0) {
        i++;
    }
    if (newInt[size] < 0) {
        size--;
    }
}

これはideoneのデモです。

leftand を使用するのではなく、 andrightポインターのより読みやすい識別子を使用iして、このループを書き直すことができますsize。これにより、アルゴリズムがコード内でより「対称」に見え、設計の対称性が認識されます。

int left = 0, right = newInt.Length-1;
while (left < right) {
    if (newInt[left] < 0 && newInt[right] >= 0) {
        int temp = newInt[left];
        newInt[left] = newInt[right];
        newInt[right] = temp;
        right--;
        left++;
        continue;
    }
    if (newInt[left] >= 0) {
        left++;
    }
    if (newInt[right] < 0) {
        right--;
    }
}

これは代替実装へのアイデアリンクです。

于 2013-01-06T04:43:37.903 に答える
3

この解決策を試してください：

var newInt = new[] {5, -2, -1, -4, -20, 6, 7, -14, 15, -16, 8, 9, 10};
var solution = newInt.GroupBy(i => i > 0).
    SelectMany(g => g).
    ToArray();

アルゴリズムの問​​題は、 を減らすsizeと、newInt[size]ポイントが負の値になり、ifブロックに入らないことです。

于 2013-01-06T04:38:16.010 に答える
1

非常に簡単で簡単な解決策の一般的なアイデアは、1 つのインデックスを開始し、それleftを配列の先頭で呼び出し、別のインデックスを配列rightの最後で呼び出すことです。

left負の数が見つかるまで、または までインクリメントしますleft == right。right負の数に達したら、正の数が見つかるまで、または になるまでデクリメントしますright == left。

leftが負の数のインデックスを作成し、正の数のインデックスを作成している場合はright、2 つの項目を入れ替えて、left再度インクリメントを開始します。

テストされていない一般的なアイデア：

int left = 0;
int right = a.Length-1;
while (left < right)
{
    if (a[left] < 0)
    {
        while (right > left)
        {
            if (a[right] >= 0)
            {
                // swap here
                int temp = a[left];
                a[left] = a[right];
                a[right] = temp;
                break;
             }
             --right;
        }
    }
    ++left;
}
于 2013-01-06T05:12:57.603 に答える
1

これにより、最小限のループで目的の順序が得られます

int[] newInt = new int[] { 5, -2, -1, -4, -20, 6, 7, -14, 15, -16, 8, 9, 10 };
int lt = 0;
int rt = newInt.Length - 1;
while (true) {
    // Find first negative number
    while (newInt[lt] >= 0 && lt < rt) {
        lt++;
    }

    // Find last positive number
    while (newInt[rt] < 0 && rt > lt) {
        rt--;
    }

    if (lt == rt) {
        break; // Finished
    }

    // Swap
    int temp = newInt[lt];
    newInt[lt] = newInt[rt];
    newInt[rt] = temp;
}
//TODO: Print result
于 2013-01-06T05:18:48.837 に答える
0

ジェネリックとlinqを使用できる場合、最も簡単な解決策は次のとおりです。

int[] newInt = new int[] { 5, -2, -1, -4, -20, 6, 7, -14, 15, -16, 8, 9, 10 };
newInt.ToList().Sort();
newInt.Reverse();
newInt = newInt.ToArray();

これが役立つことを願っています!!

于 2013-01-06T04:33:23.953 に答える