跳到主要内容

846.一手顺子

· 阅读需 4 分钟

1、题干​

Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。

给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌上的数值。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。

 

    示例 1：

    输入：hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
    输出：true
    解释：Alice 手中的牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。

    示例 2：

    输入：hand = [1,2,3,4,5], groupSize = 4
    输出：false
    解释：Alice 手中的牌无法被重新排列成几个大小为 4 的组。

     

    提示：

    • 1 <= hand.length <= 104
    • 0 <= hand[i] <= 109
    • 1 <= groupSize <= hand.length

     

    注意：此题目与 1296 重复：https://leetcode-cn.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

    2、解法1​

    先对原数组升序排序，然后进行双指针嵌套遍历，外层遍历找顺子起点，内层遍历找顺子后续元素，被找到的元素置为-1即寻找其他顺子元素时直接略过，若无法找到完整顺子则返回false

    3、代码​

    var isNStraightHand = function (hand, groupSize) {
        hand.sort((a, b) => a - b);
        for (let i = 0; i < hand.length; i++) {
            if (hand[i] < 0) continue;
            let count = 0;
            for (let j = i + 1; j < hand.length && count !== groupSize - 1; j++) {
                if (hand[j] - hand[i] === count + 1) count++, hand[j] = -1;
            }
            if (count !== groupSize - 1) return false;
        }
        return true;
    };

    代码逻辑简要说明

    • 外层遍历：从下标i=0开始遍历数组内的元素，如果当前元素不为负数则作为顺子起点
    • 内层遍历：从下标j=i+1(即顺子起点的下一个元素)开始遍历数组内的元素，寻找顺子后续元素
      • 对已找到的元素计数，计数变量记为count
      • 若当前元素与顺子起点的差值等于count+1，则说明该元素是顺子的后续元素
    • 内层遍历结束，若找到的元素数量不等于groupSize - 1，说明顺子不存在应返回false

    4、执行结果​

    1.png

    5、解法2​

    先对原数组升序排序，然后对数组内数字进行哈希表计数（数字作key数量作value），然后遍历数组所有数字，以数量大于1的数字作为顺子起点，寻找顺子后续元素，若无法找到完整顺子则返回false

    6、代码​

    var isNStraightHand = function (hand, groupSize) {
        hand.sort((a, b) => a - b);
        const map = hand.reduce((acc, n) => acc.set(n, (acc.get(n) || 0) + 1), new Map());
        for (const n of hand) {
            if (!map.get(n)) continue;
            for (let i = 0; i < groupSize; i++) {
                if (!map.get(n + i)) return false;
                else map.set(n + i, map.get(n + i) - 1);
            }
        }
        return true;
    };

    7、执行结果​

    执行用时: 100 ms 内存消耗: 47.1 MB