0954. Array of Doubled Pairs - kumaeki/LeetCode GitHub Wiki

0954. Array of Doubled Pairs

Given an array of integers arr of even length, return true if and only if it is possible to reorder it such that arr[2 * i + 1] = 2 * arr[2 * i] for every 0 <= i < len(arr) / 2.

Example 1:

Input: arr = [3,1,3,6]

Output: false

Example 2:

Input: arr = [2,1,2,6]

Output: false

Example 3:

Input: arr = [4,-2,2,-4]

Output: true

Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Example 4:

Input: arr = [1,2,4,16,8,4]

Output: false

Constraints:

  • 0 <= arr.length <= 3 * 10^4
  • arr.length is even.
  • -10^5 <= arr[i] <= 10^5

解法1

把0, 正数和负数分开计算.

class Solution {
    public boolean canReorderDoubled(int[] arr) {

        Arrays.sort(arr);

        Map<Integer, Integer> map = new HashMap<>();
        for (int i : arr)
            map.put(i, map.getOrDefault(i, 0) + 1);

        if (map.getOrDefault(0, 0) % 2 != 0)
            return false;

        for (int i = getMinPositive(arr); i < arr.length; i++) {
            int n1 = arr[i], n2 = arr[i] * 2;
            // 如果n1计数为0, 那么说明已经被之前的计算用掉了
            if (map.get(n1) == 0)
                continue;

            // 如果n2计数为0, 说明该数组不满足条件,返回false
            if (map.getOrDefault(n2, 0) == 0)
                return false;

            // 完成当前计算, n1和n2计数减一
            map.put(n1, map.get(n1) - 1);
            map.put(n2, map.get(n2) - 1);
        }

        for (int j = getMaxNegative(arr); j >= 0; j--) {
            int n1 = arr[j], n2 = arr[j] * 2;
            // 如果n1计数为0, 那么说明已经被之前的计算用掉了
            if (map.get(n1) == 0)
                continue;

            // 如果n2计数为0, 说明该数组不满足条件,返回false
            if (map.getOrDefault(n2, 0) == 0)
                return false;

            // 完成当前计算, n1和n2计数减一
            map.put(n1, map.get(n1) - 1);
            map.put(n2, map.get(n2) - 1);
        }

        return true;
    }
    
    // 得到最小正数的下标
    private int getMinPositive(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] <= 0)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }

    // 得到最大负数的下标
    private int getMaxNegative(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] < 0)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left - 1;
    }
}

解法2

用空间换时间.

因为最大值和最小值都只有10^5, 所以最坏情况下也只需要两个长度为10^5的数组.

class Solution {
    public boolean canReorderDoubled(int[] A) {
        int max = 0, min = 0;
        for (int a : A) {
            max = Math.max(max, a);
            min = Math.min(min, a);
        }
        int[] neg = new int[-min + 1], pos = new int[max + 1];
        int count0 = 0;
        for (int a : A) {
            if (a > 0)
                pos[a]++;
            else if (a < 0)
                neg[-a]++;
            else
                count0++;
        }

        if (count0 % 2 == 1)
            return false;
        for (int i = 0, mid = max / 2; i <= max; i++)
            if (pos[i] > 0)
                if (i > mid || pos[i * 2] < pos[i])
                    return false;
                else {
                    pos[i * 2] -= pos[i];
                    pos[i] = 0;
                }

        for (int i = 0, mid = -min / 2; i <= -min; i++)
            if (neg[i] > 0)
                if (i > mid || neg[i * 2] < neg[i])
                    return false;
                else {
                    neg[i * 2] -= neg[i];
                    neg[i] = 0;
                }

        return true;
    }
}

解法3

更简洁的解法. 基于解法1.

class Solution {
    public boolean canReorderDoubled(int[] A) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int a : A)
            map.put(a, map.getOrDefault(a, 0) + 1);
        Arrays.sort(A);
        for (int a : A)
            // 如果当前值还没有被计算过
            if (map.get(a) > 0) {
                
                // 如果是小于0的奇数, 那么直接返回false
                if (a < 0 && a % 2 == 1)
                    return false;

                // 负数的排列是按照绝对值的降序排列, 所以先出现的是2*x, 然后才是x
                // 而正数的排列是正常先x 然后是2*x
                // 所以正数是乘以2, 负数是除以2
                int t = a > 0 ? a * 2 : a / 2;
                
                // 如果目标t的个数小于a的个数, 那么不可能得到结果, 返回false
                if (map.getOrDefault(t, 0) < map.get(a))
                    return false;
                
                // 更新目标t的个数(减去a的个数)
                map.put(t, map.get(t) - map.get(a));
                // 更新a的个数
                map.put(a, 0);
            }
        return true;
    }
}