在JavaScript数组中检查数字序列的最有效方法是什么？

Question

背景

在一次技术面试中，我被要求用JavaScript实现一个缺失的算法。面试官提供了一些代码和18个失败的单元测试，一旦成功实现算法，这些测试就会通过。我相信有更有效率的解决方法，因为我在规定时间内尝试了几种不同的方法。这是我首先想到的解决方案，虽然对于技术测试来说足够，但我想知道更好的解决方法。

问题

判断扑克牌手中的牌是否形成顺子。（我已经按升序排序了手中的牌。）

我的解决方案

PokerHand.prototype._check_straight_function = function(arr) {
    var isStraight = false;
    for (var j = i = 4; i >= 0 && j > 1; i--)
        if (arr[i].value() - 1 == arr[--j].value()) {
            isStraight = true;
        } else {
            isStraight = false;
        }
    };
    return isStraight;
};

其他方法

有些我没有实现的方法，我认为可能会更快。如果有人能够向我演示下面某个方法的工作版本，并帮助我理解哪种方法最快，我将不胜感激。

• 递归使用arr.pop().value - 1 == arr.pop().value()
• 过滤数组以创建一个只包含下一个索引（arr[++i]）是当前索引+1的值的新数组，然后看新数组的长度是否相同。
• 使用for循环和break / continue来尽早中断顺子。

- Luke

---

手中的牌已排序吗？ - stinepike

看起来你的问题可能更适合于http://codereview.stackexchange.com/。 - Spencer Wieczorek

@StinePike 是的，根据这行代码（我已经按升序排列了卡片）。 - Luke

代码不正确，因为它只会针对正在检查的一对赋值或清除 isStraight。因此，“最后一对”错误地确定了结果。 - user2864740

因为数组已经排序，我们知道拥有顺子的必要条件是第一张牌和最后一张牌之间的差值恰好为四。如果您需要检查大量的数组并且其中大部分都无法通过此测试，则可以通过添加此测试来获得全局性能提升。另外注意：如果我们知道所有的牌都具有不同的值，则这成为了一个“充分”条件。 - Arnauld

Answer 1

完全没有必要分配变量isStraight。

PokerHand.prototype._check_straight_function = function(arr) {
    for (var i = i = 4; i++) {        
        if (arr[i].value() - 1 != arr[i-1].value()) {
            return false;
        }
    };

    return true;
};

- bestprogrammerintheworld

---

谢谢。你说的返回条件是什么意思？return true 就像是 continue，而 false 就像是 "break" 是吗？（取决于你代码的其他部分） - bestprogrammerintheworld

жҲ‘зҡ„ж„ҸжҖқжҳҜдҪ иғҪеҗҰеҸӘиҝ”еӣһforеҫӘзҺҜдёӯзҡ„ifиҜӯеҸҘзҡ„еҖјеҗ—пјҹдҫӢеҰӮпјҡreturn arr[i].value() - 1 == arr[i-1].value()еҒҮи®ҫеҰӮжһңиҝ”еӣһеҖјдёәtrueпјҢеҫӘзҺҜе°Ҷ继з»ӯжү§иЎҢпјҢ并еңЁжқЎд»¶дёәfalseж—¶зҹӯи·ҜгҖӮ - Luke

我不明白。你想要返回什么值（以及为什么）？ - bestprogrammerintheworld

如果返回false将短路循环，而返回true将继续执行，那么你需要if语句吗？ - Luke

if语句用于检查条件是否告诉“这不是一个有序数字序列吗？-然后返回false...”如果它是一个有序数字序列-它将继续for循环。在for循环之后返回true，因为我们确信数组中的所有项目都按升序编号排序。所以是的，false会短路循环并返回true将继续它。 - bestprogrammerintheworld

Answer 2

仅仅是提出来，我认为这个方法只需要三行代码就能实现，但是否更好则因人而异，可能会不那么清晰易懂。

    var last = arr.pop().value(), popped;
    while ((popped = arr.pop().value()) === --last);
    return popped === undefined;

- chiliNUT

---

不太易读，但实现很酷，而且是一种替代方案 :-) - bestprogrammerintheworld

谢谢！这看起来有点疯狂，但它使用了像 OP 所想的 pop，并且我很少能够使用没有主体的循环，所以我在这里很享受使用一个。 - chiliNUT

我喜欢这个，谢谢。我认为弹出实现看起来会很相似。 - Luke

Answer 3

这是另一种方法。

var isOrdered = true;
[5, 6, 8, 9].sort(function(a, b) {
  (b - a != 1) ? isOrdered = false: true;
});
alert(isOrdered);

DEMO

的英译中，保留了HTML格式，不进行解释。

- Nageshwar Reddy Pandem

---

这完全是错误的。 - adiga

Answer 4

原始代码不正确，因为它只会为正在检查的给定对分配isStraight（或清除它）。 因此，“最后一对”错误地确定了结果。

在我的书中，“更好的方法”是保持干净：

for (var i = 0; i < 4; i++) {
    var a = arr[i];   // arr[0..3]
    var b = arr[i+1]; // arr[1..4]
    if (!(a.value() + 1 == b.value())) {
        return false; // Not sequential
    }
};
return true;

如果有一个zip高阶函数可用，这可以被简化为以下变体。

arr.zip(function (a, b) { return [a.value(), b.value()] })
   .every(function (x) { return x[0] + 1 === x[1] })

但是zip不是标准的。

- user2864740

---

这不是一个答案。应该作为评论发布。 - bestprogrammerintheworld

我已经修复了错误，这是因为我编写代码来通过测试而不是解决问题。:$ 不过我确实喜欢高阶函数的想法。 - Luke

我喜欢 ! 取反符号，它使得 a.value() + 1 == b.value() 更加清晰易懂。+1 - Luke

Answer 5

这里有一段类似的代码，经过一些小优化（使用Java编写，请检查算法）。

    boolean isStraight = true;
    for (int i = 0; i < 4; i++) {
        if (arr[i] + 1 != arr[i+1]) {
            isStraight = false;
            break;
        }
    };

- stinepike

Answer 6

好的，这可能会更加整洁一些。我没有看到忍者的方法；（就比较解决方案而言-我是雇主，对于我来说，我更喜欢清晰优雅的答案，而不是比稍微快几个纳秒的答案：）

for (var i = 0; i < 5; i++) {
  if (a[i].value() != i + a[0].value())
    return false;
}
return true;

- NessBird