9

假设，我有一个n整数维数组（因为n=1它是一个向量，因为n=2它是一个矩形矩阵，因为n=3它是一个平行六面体等）。我需要对数组的元素重新排序，以便每一行、每一列等中的元素都处于非递减顺序。

  • 任何输入数组都可以吗？
  • 任何输入数组所需的排序是否唯一？我刚刚意识到这个问题的答案通常是否定的，例如对于方阵。
  • 对于在所有维度上具有不同长度的任何输入数组，所需的排序是否唯一？
  • 产生所需排序的最快算法是什么？
4

2 回答 2

3

任何输入数组都可以吗？

是的，如果我们将数组视为具有相同数量元素的单维数组，然后对其进行排序，通过将其遍历回原始 n 维数组，它仍然是排序的，因为对于 each i1,....,i_k,...,i_m: for all i_k < i_k'：

i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k) + ... < i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k') + ...
Thus (the array is ordered):
arr[i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k) + ...] < arr[ i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k') + ...]
Thus (back to original array):
arr[i_1][i_2]...[i_k]... < arr[i_1][i_2]...[i_k']...

至于第二个问题：

对于在所有维度上具有不同长度的任何输入数组，所需的排序是否唯一？

不：

1 1          1 3
3 4          1 4
5 6          5 6

产生所需排序的最快算法是什么？

已经提出了一种解决方案：认为它是一个很大的长数组并对其进行排序。复杂性是O(n_1*n_2*...*n_m*log(n_1*n_2*...*n_m))
我的直觉说，如果你能做得更快，那么你可以更快地发脾气O(nlogn)，但我没有证据证明这种说法，所以它可能是错误的。

于 2013-08-05T18:03:45.743 回答
1

让我详细说明一下 Alptigin Jalayr 的想法。

假设我们对行进行了排序，因此对于以下数据，我们有a <= b和c <= d。

     .       .
..., a, ..., b, ...
     .       .
..., c, ..., d, ...
     .       .

当a大于c, 即c <a, 那么它们的交换给了我们c < bsincea <= b和a <=dsince b <= d（如果b > d, 我们也交换band d）。总之，先对行进行排序，然后再对列进行排序可以为您提供所需的矩阵。

于 2013-08-05T18:06:54.600 回答