作者s25g5d4 (function(){})()
看板Ajax
标题Re: [ js ] chrome 的 Math.random() 好固定的感觉
时间Mon Jun 26 21:21:30 2017
上面原因有人解释过了
这里提供一个简单的解法：
Array(N)
.fill()
.map( (v,i) => [ ++i, Math.random() ] )
.sort( (a,b) => a[1] - b[1] )
.map( (x) => x[0] )
写成白话文(?)的话大概是这样
var arr = [];
for (var i = 0; i < N; ++i) {
arr[i] = [ i + 1, Math.random() ];
}
arr.sort(function compare(a, b) {
return a[1] - b[1];
});
for (i = 0; i < N; ++i) {
arr[i] = arr[i][0];
}
如果要用已经填好资料的阵列来做的话可以这样：
// dataArray contains some elements
dataArray
.map( (e) => [e, Math.random()] )
.sort( (a, b) => a[1] - b[1] )
.map( (e) => e[0] )
翻成白话文：
for (var i = 0; i < dataArray.length; ++i) {
dataArray[i] = [ dataArray[i], Math.random() ];
}
dataArray.sort(function compare(a, b) {
return a[1] - b[1];
}
for (i = 0; i < dataArray.length; ++i) {
dataArray[i] = dataArray[i][0];
}
原解法作者：Dominic Wu
讨论串：
https://www.facebook.com/groups/f2e.tw/permalink/1326307397406622/
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.33.238.141
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Ajax/M.1498483294.A.097.html
1F：推 LPH66: 这就是我推文说的「给每个元素一个乱数值再用它排序」方法 06/26 21:38
2F：→ LPH66: 之所以要这样做的原因还是在於比较函式的全序性 06/26 21:39
3F：→ LPH66: 虽然谁大谁小要随机, 但给定两个东西要回传一致的结果 06/26 21:39
4F：→ LPH66: *给定同样的两个东西 06/26 21:40
5F：→ LPH66: 然後其实我还漏讲了一个条件是递移性 06/26 21:40
6F：→ LPH66: 也就是你的比较函式必须要能够当 a>b, b>c 时保证 a>c 06/26 21:41
7F：→ LPH66: 很多常见的演算法是靠着这个条件才得以快速排序 06/26 21:42
8F：→ LPH66: 这两个条件单纯回传 1 / -1 的乱数函式是无法达成的 06/26 21:43
9F：推 Kenqr: 用sort处理的时间复杂度是O(NlogN)，且需要使用temp array 06/27 10:15
11F：→ Kenqr: 时间复杂度是O(N)，应该是一般使用的正规方法。 06/27 10:16
12F：→ Kenqr: 另外下面有人提到类似原原po的方法，但作者自己承认错了XD 06/27 10:16
13F：→ s25g5d4: 其实这解法的优点是可以写成一行 XD 06/27 15:04
14F：→ CaptainH: 写成一行这麽重要? 简单的事情何必用复杂的方法做 06/28 00:00
15F：推 oToToT: 时间复杂度跟空间复杂度都比较高的做法OAO 06/28 13:57