编写算法需要帮助

Question

以下是问题的描述：

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

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

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

无效的输出将是1123、4444、244。

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

- Srini Kandula

---

如果这是一份作业，请将其标记为作业。 - Karel Petranek

要使用哪种编程语言？另外，你尝试过什么？ - BoltClock

1234也算随机顺序吗？这是最容易生成的。如果不是，请定义“随机”。 - H H

是的！听起来像是作业！我同意 Henk 的观点：你所说的随机具体指什么？ - Saher Ahwal

这不就是对1到N的数字进行简单洗牌吗？http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle - Kobi

这肯定是一份作业，所以我重新打标签了..... :-) - MD Sayem Ahmed

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

- Srini Kandula

---

你使用min和max做的那件事似乎是不必要的。 - Ben Schwehn

HashSet 不是无序的吗？这不会打破它的作用吗？ - Svante

@Ben：你说得对，我错过了实际问题的一个小部分。谢谢。 - Srini Kandula

@Svante：我不在乎顺序，但需要确保没有重复项。你认为哪个选项更好？ - Srini Kandula

问题描述中提到“随机排序”。HashSet中的物品“顺序”不是随机的，而是由哈希实现预先确定的；您应该将这个顺序视为不存在，这与“随机”完全不同。您应该使用一个有定义顺序的集合，例如ArraySet。实际上，您应该只是使用一个数组，按顺序放入数字，最后进行一个无偏差的洗牌即可。 - Svante

Answer 2

这里有一个提示：查找一下 Fisher-Yates 洗牌算法。

- Svante

Answer 3

你正在对一个整数数组进行洗牌。

这里是对Knuth shuffle的解释。

- Gilbert Le Blanc