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