leetcode （X of a Kind in a Deck of Cards）

Title：X of a Kind in a Deck of Cards    914

Difficulty：Easy

原题leetcode地址：https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/

 

1.  方法比较丑陋：将每个数出现的次数存入到Map中，判断Map的长度，再将Map中的value存入到List中，对List中的数进行求最大公约数

时间复杂度：O(n)，多次一层循环，需要遍历整个数组。

空间复杂度：O(n)，申请Map、List。

    /**
     * 1、将每个数出现的次数存入到Map中，判断Map的长度，再将Map中的value存入到List中，对List中的数进行求最大公约数
     * @param deck
     * @return
     */
    public static boolean hasGroupsSizeX(int[] deck) {

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < deck.length; i++) {
            if (map.containsKey(deck[i])) {
                map.put(deck[i], map.get(deck[i]) + 1);
            }
            else {
                map.put(deck[i], 1);
            }
        }

        if (map.size() == 1) {
            if (map.get(deck[0]) > 1) {
                return true;
            }
            else {
                return false;
            }
        }

        List<Integer> list = new ArrayList<>();
        for (Integer key : map.keySet()) {
            list.add(map.get(key));
        }

        int minX = Integer.MAX_VALUE;
        for (int i = 0; i < list.size() - 1; i++) {
            int x = getGcd(list.get(i), list.get(i + 1));
            if (x < minX) {
                minX = x;
            }
        }

        if (minX == 1) {
            return false;
        }
        else {
            return true;
        }

    }

    /**
     * 求最大公约数
     * @param num1
     * @param num2
     * @return
     */
    private static int getGcd(int num1, int num2) {

        int gcd = 0;

        if (num1 < num2) {
            num1 = num1 + num2;
            num2 = num1 - num2;
            num1 = num1 - num2;
        }

        if (num1 % num2 == 0) {
            gcd = num2;
        }

        while (num1 % num2 > 0) {
            num1 = num1 % num2;

            if (num1 < num2) {
                num1 = num1 + num2;
                num2 = num1 - num2;
                num1 = num1 - num2;
            }

            if (num1 % num2 == 0) {
                gcd = num2;
            }
        }

        return gcd;

    }