※ 引述《[email protected] (Bug J.)》之铭言： : ==> 在 [email protected] (喔喔) 的文章中提到: : > 这是在网路上看到的一个面试问题，不过我一直想不出来解法。 : > 给你一个长度为2n的阵列，其中元素为a1, a2, ..., an, b1, b2, ..., bn : > 写一个程式把这个阵列转换成a1, b1, a2, b2, ..., an, bn : > 时间限制是O(n)，空间限制是O(1)。 : > 我尝试用in-place rearrangement的方法去做，但是没办法成功。 : > 有什麽好的办法嘛？ : kunth shuffle 不对吧? 根据维基百科 http://en.wikipedia.org/wiki/Shuffling#Shuffling_algorithms The second, generally known as the Knuth shuffle or Fisher-Yates shuffle, is a linear-time algorithm which involves moving through the pack from top to bottom, swapping each card in turn with another card from a random position in the part of the pack that has not yet been passed through (including itself). Providing that the random numbers are unbiased, this will always generate a random permutation. 这并不是原PO要的shuffle... (而且你还把人家Knuth的名字拼错了= =) -- 'Oh, Harry, dont't you see?' Hermione breathed. 'If she could have done one thing to make absolutely sure that every single person in this school will read your interview, it was banning it!' ---'Harry Potter and the order of the phoenix', P513 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 219.84.44.21