原文链接: https://leetcode-cn.com/problems/array-of-doubled-pairs

英文原文

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

 

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:

• 2 <= arr.length <= 3 * 104
• arr.length is even.
• -105 <= arr[i] <= 105

中文题目

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。

 

示例 1：

输入：arr = [3,1,3,6]
输出：false

示例 2：

输入：arr = [2,1,2,6]
输出：false

示例 3：

输入：arr = [4,-2,2,-4]
输出：true
解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]

示例 4：

输入：arr = [1,2,4,16,8,4]
输出：false

 

提示：

• 0 <= arr.length <= 3 * 104
• arr.length 是偶数
• -105 <= arr[i] <= 105

通过代码

官方题解

想法

如果 x 是当前数组中绝对值最小的元素，那么它一定会配对 2*x，因为不存在 x/2 可以和它配对。

算法

直接改写最后的结果数组。

按照绝对值大小检查整个数组。当检查到元素 x 并且没有被使用时，它一定要配对 2*x。我们将尝试记录 x，2x。如果没有元素 2x 则返回答案 false。如果所有元素都被访问，答案是 true。

为了记录哪些元素还没有被访问，可以用 count 来记录。

[]
class Solution {
    public boolean canReorderDoubled(int[] A) {
        // count[x] = the number of occurrences of x in A
        Map<Integer, Integer> count = new HashMap();
        for (int x: A)
            count.put(x, count.getOrDefault(x, 0) + 1);

        // B = A as Integer[], sorted by absolute value
        Integer[] B = new Integer[A.length];
        for (int i = 0; i < A.length; ++i)
            B[i] = A[i];
        Arrays.sort(B, Comparator.comparingInt(Math::abs));

        for (int x: B) {
            // If this can't be consumed, skip
            if (count.get(x) == 0) continue;
            // If this doesn't have a doubled partner, the answer is false
            if (count.getOrDefault(2*x, 0) <= 0) return false;

            // Write x, 2*x
            count.put(x, count.get(x) - 1);
            count.put(2*x, count.get(2*x) - 1);
        }

        // If we have written everything, the answer is true
        return true;
    }
}

[]
class Solution(object):
    def canReorderDoubled(self, A):
        count = collections.Counter(A)
        for x in sorted(A, key = abs):
            if count[x] == 0: continue
            if count[2*x] == 0: return False
            count[x] -= 1
            count[2*x] -= 1

        return True

算法复杂度

• 时间复杂度：$O(N \log{N})$，其中 $N$ 是数组 A 的长度。
• 空间复杂度：$O(N)$。

统计信息

通过次数	提交次数	AC比率
7359	24307	30.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言