一个打乱数组顺序的问题
前几天我去笔试,有道题是给你一个数组,然后数组乱序,输出,然后想了一个方法,就是自定义一个交换方法,然后通过一个随机数控制交换循环的次数,就会产生和原数组不一样的结果,但是这样做会很大几率和原来的数组一样,想问下大神们有啥好的方法?
------解决方案--------------------
其实简单点,从数组第一个元素循环到最后一个元素,每次将当前元素跟一个随机选择的元素交换即可。
时间复杂度比较固定就是:O(n)。
最后,你说的“会很大几率和原来的数组一样”,我觉得你那种方式,只要保证交换次数足够多(跟原数组大小相比,比如2倍以上),应该是很小几率。
------解决方案--------------------洗牌算法。
------解决方案--------------------按随机索引,排除已经拿出来的那个索引,好处是都不用动数组,只需动索引顺序就ok