考研未遂后，一直没有时间，也没有心情来更新博客，没法读研只能找工作了，在春季校招中实在没什么好公司，之前投的大狗腾和美团简历也果断被刷，被迫走向社招，还好拿了一个在春招里还算满意的offer。接下来还有一个月毕业答辩，毕设一点没弄，可能这段时间写博客时间同样也会比较少。言归正传，这几天弄点小东西有一个需求是随机遍历数组，我思考的一下，写了两种算法：
1.首先直接想到的是利用hash生成一个随机索引序列，来遍历数组
代码清单：
[java]
import java.util.HashSet;
import java.util.Random;
public class RandomVisitArray {
public static void main(String[] args){
RandomVisitArray robot = new RandomVisitArray();
int[] a = {1,2,3,4,5,6};
robot.visit(a);
}
public void visit(int[] a){
Random random = new Random();
HashSet set = new HashSet();
int[] index_array = new int[a.length];
int index = 0;
while(set.size() < a.length){
int random_index = random.nextInt(a.length);
if(!set.contains(random_index)){
set.add(random_index);
index_array[index++] = random_index;
}
}
for(int i = 0; i < index_array.length; i++){
System.out.print(a[index_array[i]] + " ");
}
}
}
import java.util.HashSet;
import java.util.Random;
public class RandomVisitArray {
public static void main(String[] args){
RandomVisitArray robot = new RandomVisitArray();
int[] a = {1,2,3,4,5,6};
robot.visit(a);
}
public void visit(int[] a){
Random random = new Random();
HashSet set = new HashSet();
int[] index_array = new int[a.length];
int index = 0;
while(set.size() < a.length){
int random_index = random.nextInt(a.length);
if(!set.contains(random_index)){
set.add(random_index);
index_array[index++] = random_index;
}
}
for(int i = 0; i < index_array.length; i++){
System.out.print(a[index_array[i]] + " ");
}
}
}
这种方法的缺点也是显然的，随着序列的增长，重复的概率越来越大，比如对于大小为100的数组，每次取元素的成功的概率一次为100%，99%，......2%,1%。所以循环次数的期望值为（1+2+...+99+100）所以时间复杂度为O（n*（n+1）/2) = O(n^2).显然这样的结果是不令人满意的。
2.我的第二种思路是：先随意生成0..n-1之间的一个数，然后与数组最后一个数交换，然后随机生成0..n-2之间一个树，与数组倒数第二个数交换。直到整个数组遍历结束，显然这个算法的时间复杂度是O(n).
代码清单：
[java]
import java.util.Random;
public class RandomVisitArray {
public static void main(String[] args){
RandomVisitArray robot = new RandomVisitArray();
int[] a = {1,2,3,4,5,6};
robot.visit2(a);
}
public void visit(int[] a) {
int index = a.length;
Random random = new Random();
while(index > 0){
int random_index = random.nextInt(index--);
System.out.print(a[random_index] + " ");
a[random_index] ^= a[index];
a[index] ^= a[random_index];
a[random_index] ^= a[index];
}
}
}
import java.util.Random;
public class RandomVisitArray {
public static void main(String[] args){
RandomVisitArray robot = new RandomVisitArray();
int[] a = {1,2,3,4,5,6};
robot.visit2(a);
}
public void visit(int[] a) {
int index = a.length;
Random random = new Random();
while(index > 0){
int random_index = random.nextInt(index--);
System.out.print(a[random_index] + " ");
a[random_index] ^= a[index];
a[index] ^= a[random_index];
a[random_index] ^= a[index];
}
}
}
这个算法的缺点是破坏的原数据结构，解决的方法是用类似的思想生成一个不重复的随机索引序列。
这个问题类似于洗牌算法，我想还会有一些其他的巧妙算法。