我想检查n
数组在JavaScript中是否都包含相同的整数?最有效的方法是什么?
发布于 2018-10-02 14:00:51
如果数组中只有数字-使用基本CRC算法的一些变化复杂度是每个数组的O(n),那么它将是最快的check。
类似的思想,计算和(数组)和乘积(数组),你可以用O(n)计算这两个值。例如:
1, 5, 6, 7 ,8 sum=27, prod=1680
7, 8, 1, 5, 6 sum=27, prod=1680
但
3, 8, 5, 5, 6 sum=27, prod=3600
注:特例是0!因为这将使产品无效,所以所有的值都应该使用+1。
NOTE2要记住,CRC算法背后的思想是使用一个字节或dword变量来表示总数,并且变量最终会溢出。
例如,在字节: 250 + 10 = 5的情况下,字节在255处溢出。但是,这是可以的,因为两个数组都会溢出,出现错误报告的可能性很小。我相信,如果我们能努力,我们可以证明它在数学上,这是可以的。
然而,如果你懒得做数学和绝对肯定是必需的,你可以使用这种方法快速过滤所有的消极候选人,然后sort+compare只有积极的候选人。仍然要比只使用sort+compare快得多。
NOTE3:刚刚意识到您使用的是JS,JS与大数字有点混乱,算术运算没有溢出。
但是,它确实溢出了逻辑运算符,CRC算法确实使用了xor,所以您很好。这是CRC algo:check
这是一些开源的实现: prima上的https://github.com/emn178/js-crc/blob/master/src/crc.js似乎遵循了算法,但是我不确定它的质量如何,所以您的尽职调查吧!
https://stackoverflow.com/questions/52616603
复制