2

我需要在 Java 中尽可能高效地生成 0 到 1000 之间的非重复随机数列表。我现在只有 2 个想法,想知道是否还有其他更好的想法,如果没有,我应该使用以下哪些想法?

    • 生成一个介于 0 到 1000 之间的随机数 r,并将其添加到另一个名为 randomArray[r] 的数组中,索引为 r
    • 生成另一个随机数并检查 randomArray[r] 是否尚未存储先前生成的随机数
    • 继续,直到我完成
    • 生成一个数组并用它的索引填充它的元素
    • 像疯了一样洗牌(另外,我怎样才能有效地做到这一点?)
    • 从头开始使用数组中的元素值。

谢谢!

4

2 回答 2

2

java.util.Collections.shuffle方法以相等的可能性随机播放列表。创建一个列表并添加从 0 到 1000 的值。然后使用此方法打乱列表。

List l = new ArrayList();
for(int i = 0; i <= 1000; i++)
    l.add(i);

Collections.shuffle(l); 

现在列表包含洗牌后的值。

于 2013-07-14T03:45:19.140 回答
1

尝试使用LinkedHashSet<Integer>(参见文档)。

常规HashSet<Integer>存储一组Integers 有效:放置一个新数字并检查一个数字是否已经存在是在恒定时间内完成的(当将数字存储在数组中时,正如您所提到的,这些查找需要线性时间来检查)。

现在,既然你说你想要一个数字列表,我们使用 aLinkedHashSet<Integer>它具有常规的所有属性HashSet<Integer>,并且还保证如果你循环遍历元素,你将始终以相同的顺序遍历它们。

代码看起来像这样:

Set<Integer> randomNumberList = new LinkedHashSet<Integer>();

int r;

// Make sure the number is not present in the list, and then add it:
do {
  r = ... // Generate your next random number
} while( randomNumberList.contains(r) );

// At this point, we know r is not in the list, so add it:
randomNumberList.add(r);

// Do the previous as many times as you want.

// Now, to iterate over the list:
for(Integer number : randomNumberList) {
  // Do something...
}

请注意,如果您想确保确实将数字添加到列表中,则do-循环是必需的。while

于 2013-07-14T04:08:22.837 回答