4

私は 14x14 の配列を持っており、各要素はバイナリ パックされた情報であり、アンパックすると A と B の 2 つのパラメーターが得られます (ここでの説明を簡単にするために、パラメーターを A:B の形式にしましょう)。 A が上から下 (列) に増加し、B が左から右 (行) に増加するような配列。

行を B で並べ替え、次に列を A で並べ替えることを考えましたが、うまくいかないことに気付きました。行を B で並べ替えるとします。次に、列を A で並べ替えると、B の順序が台無しになる可能性があります。

何か案は?

4

1 に答える 1

5

196 要素のリスト全体を A で並べ替え、最初の行に最小の 14 A が含まれ、次の行に次に小さい要素が含まれるように要素をレイアウトできます。このようにして、ith 行のすべての要素が小さくなります。 (Aによると) 番目の行のすべての要素よりjif i > j.

次に、行ごとに移動し、B で並べ替えます。

小さな例として、(9,1) (8,2) ... (1,9) のペアで 3x3 のケースを考えてみましょう。A による並べ替えは (1,9) ... (9,1) を生成し、次のようにレイアウトします。

(1,9)  (2,8)  (3,7)
(4,6)  (5,5)  (6,4)
(7,3)  (8,2)  (9,1)

次に、各行を B で並べ替えます。B の要素の順序を変更しても、A に関する主要な仮定が崩れることはありません。これは、特定の行のすべての要素が、それより上位の行のすべての要素よりも少ないためです (たとえば、3 番目の行の最小の A行は 7 で、2 行目の最大 A は 6 です)。

次に、次のようになります。

(3,7)  (2,8)  (1,9)
(6,4)  (5,5)  (4,6)
(9,1)  (8,2)  (7,3)

編集:質問は次のように明確化されました:

わかりました、これは理にかなっていますが、これがあるとしましょう: [[-1 -1 2:8 -1 -1] [ -1 3:7 4:16 5:2 -1] [ 2:14 3: 9 2:6 5:9 1:2] [ -1 9:8 4:2 9:1 -1] [-1 -1 2:2 -1 -1]]。「-1」は null 値を表すため、ソートしないでください。最終的に並べ替えられた配列は、このような菱形のままである必要があります。

「ひし形」を維持するには、パターンに従ってマトリックスを埋めるだけです。例では:

[[-1 -1 2:8 -1 -1] [ -1 3:7 4:16 5:2 -1] [ 2:14 3:9 2:6 5:9 1:2] [ -1 9:8 4:2 9:1 -1] [-1 -1 2:2 -1 -1]]

最初に要素を引き出します

[2:8 3:7 4:16 5:2 2:14 3:9 2:6 5:9 1:2 9:8 4:2 9:1 2:2]

次に並べ替えますA(この場合、同点を解消するために B 値を使用します)。

[1:2 2:2 2:6 2:8 2:14 3:7 3:9 4:2 4:16 5:2 5:9 9:1 9:8]

次に、必要な行を作成します。パターンを見ると、行の要素数は1,3,5,3,1であるため、行は

[[1:2] [2:2 2:6 2:8] [2:14 3:7 3:9 4:2 4:16] [5:2 5:9 9:1] [9:8]]

次に、行をB値で並べ替えます。

[[1:2] [2:2 2:6 2:8] [4:2 3:7 3:9 2:14 4:16] [9:1 5:2 5:9] [9:8]]

これで、ダイヤモンドを再構築できます。

[[-1   -1   1:2  -1     -1] 
 [-1   2:2  2:6  2:8    -1] 
 [4:2  3:7  3:9  2:14 4:16] 
 [-1   9:1  5:2  5:9    -1] 
 [-1   -1   9:8  -1     -1]]

行と列が正しくソートされていることを確認してください:)

于 2013-06-16T22:01:27.317 に答える