置换数组中的行以消除不断增加的子序列

Question

以下问题取自算法问题(问题653):

你被给予了2个数字矩阵.找到一个O(n log n)算法,该算法置换数组中的行,使得数组中的任何一列都不包含比⌈√n更长的子序列(可能不包含连续的数组元素).

我不知道如何解决这个问题.我认为它可能会使用某种分而治之的复发,但我似乎无法找到它.

有没有人有任何想法如何解决这个问题？

Answer 1

Heres是我的解决方案.

1)根据第一个元素从最大到最低排序行.

1 6    5 1
3 3 -\ 3 3
2 4 -/ 2 4
5 1    1 6

2)将它分成⌈√n⌉组,剩下的组(不超过⌈√n⌉组)

5 1    5 1
3 3 -\ 3 3
2 4 -/ 
1 6    2 4
       1 6

3)根据第二个元素从最大到最低对每个组中的行进行排序

5 1    3 3
3 3    5 1
    -> 
2 4    1 6
1 6    2 4

正确性证明:

第1列中增加的子序列只能在单个组中发生(大小为<=⌈√n⌉),

第2列中没有2个增加子序列的元素属于同一组(不超过⌈√n⌉组)