1

私は最近、インタビューでこの問題に出くわしました。それを解決する最善の方法は何か知りたいと思っていました。質問には、ASCII 文字 '0' から '9' を含む char 配列が与えられ、結果の配列内の ASCII 値のセットが可能な限り低い値を形成するように 1 つのスワップが行われます。入力配列には先行する 0 がなく、結果の配列にも先行するものはありません。

以下に例を示します。char a[] = {'1','0', '9','7','6'}

ソリューション：char b[] = { '1','0', '6', '7', '9'}

もう一つの例：char a[] = {'9','0', '7','6','1'}

ソリューション： char b[] = {'1','0', '7','6','9'}

パフォーマンスの観点から最適なソリューションを探しています。スワップは 1 つしか許可されていないため、ソートは許可されていないと想定しました。私はそれを明確にしませんでした。したがって、1 つのスワップを使用するだけで取得できる最小値を探しています。ソリューションの複雑さも提供していただけると助かります。

4

4 に答える 4

1

アルゴリズム：

先頭に 0 を付けることができないため、0 は個​​別に処理する必要があることに注意してください。

ゼロ以外の最小数を追跡しながら、右から移動します。最初の 0 も記録します。

記録されたゼロ以外の数値よりも大きい数値を見つけた場合は、その 2 つをこれまでで可能な最良のスワップとして記録します。

ゼロを見つけたら、ここからゼロ以外の先頭文字を記録し、ゼロの可能な限り最良のスワップとして記録します。

上記のスワップのいずれかの品質を比較していないことに注意してください。より左の位置にスワップする方が常に良いため、現在の最高のものを新しいものに置き換えるだけです.

完了したら、ゼロの最適なスワップと非ゼロの最適なスワップの目標位置を比較し、最も左の位置を選択するか、同じ場合はゼロを選択します。

可能なスワップが見つからない場合、配列はすでに指定された数値の最小順列であるため、何もしません。または、必要に応じて、右端の 2 文字を入れ替えます。

実行時間：

O(n).

例：

入力: 10976

Processing  6   7   9   0   1
Minimum     6   6   6   6   1
Best swap   -   6+7 6+9 6+9 6+9
Zero?       No  No  No  Yes Yes
Best 0 swap -   -   -   -   -

したがって、最良のスワップは 6/9 で、10679 になります。

入力: 3601

Processing  1   0   6   3
Minimum     1   1   1   3
Best swap   -   -   1+6 1+3
Zero?       No  Yes Yes Yes
Best 0 swap -   -   0+6 0+6

ここで可能なスワップは 1/3 と 0/6 です。
1/3 スワップの場合、ターゲット ポジションは 0 (0-indexed) です。
0/6 スワップの場合、ターゲット ポジションは 1 です。
したがって、1/3 スワップを選択すると、1603 になります。

于 2013-10-02T08:36:47.280 に答える
0

あなたが最高とはどういう意味かによります。b の最初の項目として '0' を除く最小の数字を取り出し、残りを昇順に並べ替えます。

于 2013-10-01T21:39:58.207 に答える
0

少なくとも一度は配列を通過する必要があることは明らかだと思います。最小値を見つけるには、これを行う必要があります。

また、条件を満たす値を見つける必要があります。ポスターによると、入力配列には先頭要素として「0」が含まれません。

一度に 1 つの位置で配列をループします。最小値 (最初のスポットではゼロ以外、その他のスポットでは任意) を持ち、他のどのスポットよりも小さい別の位置を探しています。 

for (pos = 0; pos < array_size-1; pos++) {
        low_index = pos;
        min_value = (pos == 0) ? '1' : '0';

        for (i = pos+1; i < array_size; i++) {
                if (min_value <= array[i]) && (array[i] < array[low_index])) {
                        low_index = i;
                }
        }

        if (low_index != pos) {
                low_value = array[pos];
                array[pos] = array[low_index];
                array[low_index] = low_value;
                break;
        }
}
于 2013-10-01T21:58:34.430 に答える