K******g
发帖数: 1870 | 1 这个题目是Column2的第7题。
大概意思是transpose一个matrix。个人觉得把(x,y)与（y,x)交换一下不就得了，复杂
度就是把matrix遍历一遍。
但是答案给出一个很“novel”的解法，先把matrix按照column sort一遍，然后在每个
相同的column里按row sort一遍。这个方法的确有意思，但是复杂度明显比前一个方法
大啊。
我实在不知道这道题的玄机在哪里。请看明白的指点一下。多谢了 |
t****a
发帖数: 1212 | 2 Please paste the problem. |
c******n
发帖数: 4965 | 3 continuous memory access, better cache coherency
【在 K******g 的大作中提到】
: 这个题目是Column2的第7题。
: 大概意思是transpose一个matrix。个人觉得把(x,y)与（y,x)交换一下不就得了，复杂
: 度就是把matrix遍历一遍。
: 但是答案给出一个很“novel”的解法，先把matrix按照column sort一遍，然后在每个
: 相同的column里按row sort一遍。这个方法的确有意思，但是复杂度明显比前一个方法
: 大啊。
: 我实在不知道这道题的玄机在哪里。请看明白的指点一下。多谢了
|
s*********t
发帖数: 1663 | 4 高深！
【在 c******n 的大作中提到】
: continuous memory access, better cache coherency
|
K******g
发帖数: 1870 | 5 对，想通了
还有可能是那个矩阵太大了，放在disk上，如果那样子的话，sort可能会快很多
【在 c******n 的大作中提到】
: continuous memory access, better cache coherency
|
