LeetCode846.一手顺子：「哈希计数 & 排序 (堆) & 贪心」&「双指针 & 排序」&「DFS & 排序」

浏览次数 : 次 2022-01-21

博文字数统计 : 2.1k字 | 阅读所需时长 : 9分

× 文章目录

1. LeetCode846.一手顺子：「哈希计数 & 排序 (堆) & 贪心」&「双指针 & 排序」&「DFS & 排序」

LeetCode846：一手顺子
- 时间：2021-12-30
- 力扣难度：Medium
- 个人难度：Medium
- 数据结构：一维数组、哈希表、小顶堆(优先队列)
- 算法：哈希计数、排序、贪心、双指针、DFS

LeetCode846.一手顺子：「哈希计数 & 排序 (堆) & 贪心」&「双指针 & 排序」&「DFS & 排序」

1. 题目描述

题目：原题链接
- Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成
- 给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一个整数 groupSize
- 如果她可能重新排列这些牌，返回 true，否则，返回 false
输入输出规范
- 输入：数组hand和表示一个顺子的个数groupSize
- 输出：布尔值，表示是否是一手顺子
输入输出示例
- 输入：[1,1,2,3,2,3], 3
- 输出：true

2. 方法一：哈希计数 & 排序 & 贪心

思路：哈希计数&排序&贪心
- 贪心：根据题意可知，组成的每个顺子的第一个元素都是局部数组的最小元素，所以需要从数组中找到最小元素，搜索其满足的顺子，满足则局部最优，进行下一个最小元素的顺子搜索，不满足时即无法组成顺子
- 排序：维护一个升序数组，便于根据贪心的思想每次取出最小的元素来组成顺子
- 哈希表计数：因为元素可能重复，所以使用哈希表计数
  - 数组哈希：适用于已知哈希大小的，一般是用元素最大值减去最小值来表示哈希的大小，本题数据范围太大，容易产生内存问题；其次还需要考虑是否超出数组索引范围：int[] hash = new int[hand[n - 1] + 1 - hand[0] + 1 + groupSize];
  - Map哈希：使用限制较少，由于维护的是key-value对，所以数据量小时反而可能更占空间
复杂度分析：n是数组大小
- 时间复杂度：$O(nlogn)$，排序为$O(nlogn)$，哈希表计数为$O(n)$，搜索顺子为$O(n*groupSize)$
- 空间复杂度
  - 数组哈希：$O(num_{max} - num_{min})$，即哈希表的空间
  - Map哈希：$O(n)$，哈希表的空间为$O(n)$

题解：数组哈希

// 方法一：哈希计数 + 排序 + 贪心 : O(nlogn)
public boolean isNStraightHand(int[] hand, int groupSize) {
    // 边界条件判断
    if (hand == null || hand.length == 0) return false;
    int n = hand.length;
    if (n % groupSize != 0) return false;
    // 排序
    Arrays.sort(hand);
    // 哈希计数
    int[] hash = new int[hand[n - 1]+1+groupSize];
    for (int num : hand) {
        hash[num]++;
    }

    // 搜索顺子
    for (int num : hand) {
        if(hash[num] == 0) continue;
        // 找到一组顺子，并将计数减一
        for (int i = 0; i < groupSize; i++) {
            if(hash[num + i] <= 0) return false;
            hash[num + i]--;
        }
    }
    return true;
}

改进版：Map哈希：避免空间问题

public boolean isNStraightHand(int[] hand, int groupSize) {
    // 边界条件判断
    if (hand == null || hand.length == 0) return false;
    int n = hand.length;
    if (n % groupSize != 0) return false;
    // 排序
    Arrays.sort(hand);
    // 哈希计数
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : hand) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    // 搜索顺子
    for (int num : hand) {
        if (map.containsKey(num)) {
            int val =  map.get(num);
            for (int i = 0; i < groupSize; i++) {
                if (!map.containsKey(num + i)) {
                    return false;
                }
                map.put(num + i, map.get(num + i) - val);
                if(map.get(num + i) < 0) {
                    return false;
                }
                if(map.get(num + i) == 0) {
                    map.remove(num + i);
                }
            }
        }
    }
    return true;
}

3. 方法二：哈希计数 & 小顶堆 & 贪心

思路：哈希计数&小顶堆&贪心
- 贪心：先确定最小元素，再搜索匹配其组成的顺子
- 小顶堆：Java中的优先队列就是一个堆结构，可以用来动态维护一个序列，并给出其最小元素
- 哈希表计数：解决元素重复问题
复杂度分析：n是数组大小
- 时间复杂度：$O(nlogn)$，小顶堆构建+堆调整为$O(nlogn)$，哈希表计数为$O(n)$，搜索顺子为$O(n*groupSize)$
- 空间复杂度：$O(n)$，哈希表和小顶堆的空间都为$O(n)$

题解

// 方法二：哈希计数 + 小顶堆(优先队列) + 贪心: O(nlogn)
public boolean isNStraightHand(int[] hand, int groupSize) {
    // 边界条件判断
    if (hand == null || hand.length == 0) return false;
    int n = hand.length;
    if (n % groupSize != 0) return false;

    // 哈希计数
    Map<Integer, Integer> map = new HashMap<>();
    // 小顶堆：优先队列动态维护最小元素
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int num : hand) {
        map.put(num, map.getOrDefault(num, 0) + 1);
        heap.add(num);
    }
    // System.out.println(Arrays.toString(heap.toArray()));

    // 搜索顺子
    while (!heap.isEmpty()) {
        int num = heap.poll();
        if(map.containsKey(num)) {
            for (int i = 0; i < groupSize; i++) {
                if(!map.containsKey(num + i)) return false;
                // 更新个数
                map.put(num + i, map.get(num + i) - 1);
                if(map.get(num + i) == 0) {
                    map.remove(num + i);
                }else if(map.get(num + i) < 0) {
                    return false;
                }
            }
        }
    }
    return true;
}

4. 方法三：DFS & 排序

思路：DFS+排序
- 同样的思路，使用排序或者小顶堆来维护最小元素
- 不使用哈希表来计数，而是直接进行搜索，为了表示当前元素是否搜索过，额外使用visit数组标记，或者直接标记为-1
- 因为每次搜索都是确定了顺子的第一张，即最小元素，搜索方向为向后升序搜索
复杂度分析：n是数组大小
- 时间复杂度：$O(n^2)$，排序为$O(nlogn)$，搜索顺子为$O(n^2)$
- 空间复杂度：$O(n)$

题解

// 方法三：DFS + 排序
public boolean isNStraightHand(int[] hand, int groupSize) {
    // 边界条件判断
    if (hand == null || hand.length == 0) return false;
    int n = hand.length;
    if (n % groupSize != 0) return false;
    // 排序
    Arrays.sort(hand);
    // 搜索顺子
    for (int i = 0; i < n; i++) {
        boolean flag = true; // 表示是否可以组成顺子
        int minVal = hand[i];
        if (minVal != -1) {
            hand[i] = -1;  // 标记当前元素是否使用过
            flag = dfs(minVal + 1, hand, i + 1, groupSize, 1);
        }
        if (!flag) return false;
    }
    return true;
}

// DFS：搜索以minVal开头是否可以组成顺子
private boolean dfs(int curVal, int[] hand, int start, int groupSize, int len) {
    if (len == groupSize) {
        return true;
    }
    while (start < hand.length) {
        if (hand[start] != -1) {
            if (hand[start] == curVal) {
                hand[start] = -1; // 使用过后就标记
                return dfs(curVal + 1, hand, start + 1, groupSize, len + 1);
            }
        }
        start++;
    }
    return false;
}

5. 方法四：双指针 & 排序

思路：双指针+排序
- 和DFS同样的思想，只不过将递归调用DFS方法去深度搜索的过程改为直接循环遍历
- 外层循环遍历元素数组，每次第一个元素都是最小元素，即一个顺子的开头
- 内层循环遍历当前元素的下一个元素到最后，用来查找是否存在其他几个元素，从而凑出一个顺子
- 因此判断条件还需要有当前顺子的元素个数等于groupSize
- 同样使用排序维护最小元素，使用标记的方式确认元素是否使用过
复杂度分析：n是数组大小
- 时间复杂度：$O(n^2)$，排序为$O(nlogn)$，搜索顺子为$O(n^2)$
- 空间复杂度：$O(n)$

题解

// 方法四：双指针 + 排序
public boolean isNStraightHand(int[] hand, int groupSize) {
    // 边界条件判断
    if (hand == null || hand.length == 0) return false;
    int n = hand.length;
    if (n % groupSize != 0) return false;
    // 排序
    Arrays.sort(hand);
    for (int i = 0; i < n; i++) {
        if(hand[i] == -1) continue;
        int len = 1; // 表示一个顺子的个数是否达到groupSize
        for (int j = i+1; j < n && len != groupSize; j++) {
            if(hand[j] == hand[i] + len) { // 找到一个满足顺子的元素
                len++;
                hand[j] = -1; // 标记
            }
        }
        if(len != groupSize) return false; // len不等于groupSize表示没有凑齐一个顺子
    }
    return true;
}

讨论

虽然使用DFS、双指针等两层循环的方式理论上复杂度为$O(n^2)$，大于使用排序、堆、哈希表的复杂度$O(nlogn)$，但是由于是否满足顺子基本上通过相邻的元素就可以判断，且搜索方向是向后搜索，所以反而会更快。

参考资料

本文作者： Chthollists
发布时间： 2022-01-21 23:09:05
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode846.一手顺子：「哈希计数 & 排序 (堆) & 贪心」&「双指针 & 排序」&「DFS & 排序」
本文链接： https://chthollists.github.io/post/e758bea.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！