954. Array of Doubled Pairs

二刷 06/2022

还是一刷写的好

Time O(NlogN) -> for sorting the array

Space O(N)

Runtime: 57 ms, faster than 63.80% of Java online submissions for Array of Doubled Pairs.

Memory Usage: 72 MB, less than 27.37% of Java online submissions for Array of Doubled Pairs.

class Solution {

    public boolean canReorderDoubled(int[] arr) {

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

        for (int a : arr) {

            count.put(a, count.getOrDefault(a, 0) + 1);

        }

        Arrays.sort(arr);

        for (int i = 0; i < arr.length && arr[i] <= 0; i++) {

            // Start from the smallest number

            if (!check(arr, i, count)) {

                return false;

            }

        }

        for (int i = arr.length - 1; i >= 0 && arr[i] > 0; i--) {

            if (!check(arr, i, count)) {

                return false;

            }

        }

        return true;

    }

    private boolean check(int[] arr, int i, Map<Integer, Integer> map) {

        int num = arr[i];

        if (!map.containsKey(num) || map.get(num) == 0) {

            return true;

        }

        if (num % 2 != 0) {

            return false;

        }

        map.put(num, map.get(num) - 1);

        int pair = num / 2;

        if (!map.containsKey(pair) || map.get(pair) == 0) {

            return false;

        }

        map.put(pair, map.get(pair) - 1);

        return true;

    }

}

 一刷

class Solution {

    public boolean canReorderDoubled(int[] arr) {

        Arrays.sort(arr);

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

        for (int a : arr) {

            int cnt = map.getOrDefault(a, 0) + 1;

            map.put(a, cnt);

        }

        // -4 -2 2 4

        for (int a : arr) {

            if (map.get(a) == 0) continue;

            if (a < 0 && a % 2 != 0) {

                return false;

            }; // e.g. -5

            int want = a > 0 ? a * 2 : a / 2;

            // remove a and want from map

            if (map.getOrDefault(want, 0) == 0) {

                return false;

            }

            map.put(a, map.get(a) - 1);

            map.put(want, map.get(want) - 1);

        }

        return true;

    }

}