algorithm - 编写算法所需的帮助

Question

这里是问题的描述

给定一个整数 N，编写一个函数返回一个大小为 N 的整数数组，其中包含从 1 到 N 的随机顺序的数字。从 1 到 N 每个数字必须出现一次并且不能重复。

• 你的算法的运行时间是多少？
• 你的算法可以改进吗？

例如:如果给定数字 4，则输出必须生成类似 4213、2413、3124 等的内容。

无效输出为 1123、4444、244。

有什么解决问题的办法吗？

Answer 1

是的，这是家庭作业。我刚刚用java写完算法，但是使用Fisher-Yates shuffle似乎效率更高。谢谢你们。下面是我的算法版本。

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;
}