下面是这个问题的描述
给定一个整数N,编写一个函数,该函数返回一个大小为N的整数数组,该数组包含从1到N的随机数。从1到N的每个数字必须出现一次,不能重复。
例如:如果给定数字4,则输出必须生成4213、2413、3124等。
无效的输出将是1123,4444,244。
有什么办法解决这个问题吗?
发布于 2010-08-07 17:06:33
这里有个提示:看看费舍-耶茨洗牌是什么。
发布于 2010-08-07 17:54:58
是的是在家工作。我刚刚用java完成了算法的编写,但是使用Fisher-Yates洗牌似乎要高效得多。谢谢大家。下面是我的算法版本。
Collection<Integer> generateNumbers(int n) {
Collection<Integer> numbers = new HashSet<Integer>();
Random rand = new Random();
int max = 0;
int min = 0;
for(int i=0;i<n;i++){
max=(max*10)+n;
min=(min*10)+1;
}
while(numbers.size()<n){
int random = rand.nextInt(max-min+1)+min;
int temp = random;
boolean good = true;
Set<Integer> digits = new HashSet<Integer>();
while(temp>0 && good){
int reminder = temp%10;
if(reminder > 0 && reminder <= n ){
digits.add(reminder);
}else
good = false;
temp/=10;
}
if(good && digits.size() == n)
numbers.add(random);
}
return numbers;
}发布于 2010-08-07 17:09:35
你要做的是洗牌一个整数数组。
以下是对克努斯洗牌的解释。
https://stackoverflow.com/questions/3431242
复制相似问题