給定一個大小為NxN的二維陣列T，其中填充了各種自然數（它們不必以任何方式排序，如下例所示。）。我的任務是撰寫一個程式來轉換陣列，使得位于主對角線上的所有元素都大于位于對角線上的每個元素，并且位于主對角線下方的所有元素都小于對角線上的每個元素.
例如：
T看起來像這樣：
[2,3,5]
[7,11,13]
[17,19,23]
可能的解決方案之一是：
[13,19,23]
[3,7,17 ]
[5,2,11]
我不知道該怎么做。有人知道應該在這里使用什么演算法嗎？
uj5u.com熱心網友回復：
- 假設矩陣是
NxN。 - 將所有
N2值放在一個陣列中。 - 使用您喜歡的任何方法（升序）對陣列進行排序。
- 在您的最終陣列中，第
(N2-N)/2一個值位于對角線下方，后續N值位于對角線下方，最終(N2-N)/2值位于對角線上方。
以下偽代碼應該可以完成這項作業：
mat <- array[N][N] // To be initialized.
vec <- array[N*N]
for i : 0 to (N-1)
for j : 0 to (N-1)
vec[i*N j]=mat[i][j]
next j
next i
sort(vec)
p_below <- 0
p_diag <- (N*N-N)/2
p_above <- (N*N N)/2
for i : 0 to (N-1)
for j : 0 to (N-1)
if (i>j)
mat[i][j] = vec[p_above]
p_above <- p_above 1
endif
if (i<j)
mat[i][j] = vec[p_below]
p_below <- p_below 1
endif
if (i=j)
mat[i][j] = vec[p_diag]
p_diag <- p_diag 1
endif
next j
next i
通過使用（相當復雜的）自定義排序運算子直接對矩陣進行排序，可以對代碼進行大量優化，因此可以“就地”排序。從技術上講，您將在矩陣索引與表示“對角線以下”、“對角線”和“對角線以上”索引的磁區索引集之間進行雙射。
但是我不確定它本身是否可以被視為一種演算法，因為它將高度依賴于所使用的語言以及您在內部如何存盤矩陣（以及如何使用迭代器/索引）。我可以用 C 撰寫一個，但我缺乏在 Python 中為您提供這樣一個運算子的知識。
Obviously, if you can't use a standard sorting function (because it can't work on anything else but an array), then you can write your own with the tricky comparison builtin the algorithm.
For such small matrixes, even a bubble-sort can work properly, but obviously implementing at least a quicksort would be better.
Elements about optimizing:
First, we speak about the trivial bijection from matrix coordinate [x][y] to [i]: i=x y*N. The invert is obviously x=floor(i/N) & y=i mod N. Then, you can parse the matrix as a vector.
This is already what I do in the first part initializing vec, BTW.
With matrix coordinates, it's easy:
- Diagonal is all cells where
x=y. - The "below" partition is everywhere
x<y. - The "above" partition is everywhere
x>y.
Look at coordinates in the below 3x3 matrix, it's quite evident when you know it.
0,0 1,0 2,0
0,1 1,1 2,1
0,2 1,2 2,2
We already know that the ordered vector will be composed of three parts: first the "below" partition, then the "diagonal" partition, then the "above" partition.
The next bijection is way more tricky, since it requires either a piecewise linear function OR a look-up table. The first requires no additional memory but will use more CPU power, the second use as much memory as the matrix but will require less CPU power. As always, optimization for speed often cost memory. If memory is scarse because you use huge matrixes, then you'll prefer a function.
In order to shorten a bit, I'll explain only for "below" partition. In the vector, the (N-1) first elements will be the ones belonging to the first column. Then, we'll have (N-2) elements for the 2nd column, (N-3) for the third, until we had only 1 element for the (N-1)th column. You see the scheme, sum of the number of elements and the column (zero-based index) is always (N-1).
I won't write the function, because it's quite complex and, honestly, it won't help so much to understand. Simply know that converting from matrix indices to vector is "quite easy".
The opposite is more tricky and CPU-intensive, and it SHOULD use a (N-1) element vector to store where each column starts within the vector to GREATLY speed up the process. Thanks, this vector can also be used (from end to begin) for the "above" partition, so it won't burn too much memory.
Now, you can sort your "vector" normally, simply by chaining the two bijection together with the vector index, and you'll get a matrix cell instead. As long as the sorting algorithm is stable (that's usually the case), it will works and will sort your matrix "in place", at the expense of a lot of mathematical computing to "route" the linear indexes to matrix indexes.
Please note that, despite we speak about bijections, we need ONLY the "vector to matrix" formulas. The "matrix to vector" are important - it MUST be a bijection! - but you won't use them, since you'll sort directly the (virtual) vector from 0 to N2-1.
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/452460.html
上一篇：Javascript排序混合字母數字陣列-字母升序，數字降序
下一篇：Pandas按相似列值排序