保持排序(数字)数字数字列表的算法
保持排序(数字)数字数字列表的算法
提问于 2022-11-28 10:22:02
假设我正在使用Math.random()生成随机数，其中可能有1000个，我希望它们按升序排列(在任何时候)。是否有一种不同的算法可以使它们始终保持排序，而无需调用排序例程？我唯一能想到的就是BST？但也许还有更好的办法。
一些代码将有助于：
const numContainer = {};
for(let i = 0; i < 1000; i++){
const r = Math.random(); // I generate a new RV
numContainer[r] = {r}; // I want to store it in order, but this isn't helping :-)
}显然，以上并不能维持任何数字顺序的钥匙等。我期待着他们被排序，因为我走。
更新：我意识到用例可能是个好消息(或者有趣)。用例是一个离散事件模拟，随机均匀变量越小，事件越早，所以我需要按数字顺序阅读事件，如果它们自然地被排序，而不是需要排序或其他什么，那就更好了。
回答 3
Stack Overflow用户
发布于 2022-11-28 12:28:32
您可以在线性时间内按排序顺序生成数字。本文描述的方法是:用Bentley & Saxe生成随机数的排序列表。
https://pdfs.semanticscholar.org/2dbc/4e3f10b88832fcd5fb88d34b8fb0b0102000.pdf
/**
* Generate an sorted list of random numbers sorted from 1 to 0, given the size
* of the list being requested.
*
* This is an implementation of an algorithm developed by Bentley and Sax, and
* published in in ACM Transactions on Mathematical Software (v6, iss3, 1980) on
* 'Generating Sorted Lists of Random Numbers'.
*/
public class SortedRandomDoubleGenerator {
private long valsFound;
private double curMax;
private final long numVals;
/**
* Instantiate a generator of sorted random doubles.
*
* @param numVals the size of the list of sorted random doubles to be
* generated
*/
public SortedRandomDoubleGenerator(long numVals) {
curMax = 1.0;
valsFound = 0;
this.numVals = numVals;
}
/**
* @return the next random number, in descending order.
*/
public double getNext() {
curMax = curMax
* Math.pow(Math.E, Math.log(RandomNumbers.nextDouble())
/ (numVals - valsFound));
valsFound++;
return curMax;
}
}Stack Overflow用户
发布于 2022-11-28 12:01:24
Stack Overflow用户
发布于 2022-11-28 13:42:50
您没有对数据结构指定任何约束，因此基本解决方案是一个数组，并结合插入新元素。
或者是一个链接的名单。
或者二进位搜索树。
但不是一堆东西！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/74599147
复制相关文章
相似问题
腾讯云开发者
