[LeetCode] 954. 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].

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。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/array-of-doubled-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题跟之前的 2007题 类似，但是我感觉比 2007 稍微麻烦一些，难点在于这道题需要处理负数。但是负数我们也可以很巧妙地解决。

根据题意，其实这道题请你判断的还是数组的重新排列，是否可以将 input 数组重新排列，从而满足某个数字和其两倍排在一起，类似这样 [x, 2x, y, 2y, ......]。所以思路还是需要用到 hashmap 统计每个数字分别出现了几次，这里我们还需要用一个 list，将 hashmap 中 unique keys 拿出来，并按照数字的绝对值从小到大排列，这样我们就可以处理负数的部分了。如果遇到的数字是0，则判断0出现的次数是否是偶数次；如果遇到的数字是正数或者负数，则需要判断当前数字 X 的出现次数起码不能大于 2X 的出现次数，满足这个条件后，我们再从hashmap中对 key 为 2X 的那个元素减去 X 的出现次数，说明有若干个 2X 已经抵消了。

时间O(n + klogk) - 将 n 个数字加入 hashmap + 对 k 个 unique key 排序

空间O(n)

Java实现

 1 class Solution {
 2     public boolean canReorderDoubled(int[] arr) {
 3         int len = arr.length;
 4         // corner case
 5         if (len % 2 == 1) {
 6             return false;
 7         }
 8         
 9         // normal case
10         HashMap<Integer, Integer> map = new HashMap<>();
11         for (int num : arr) {
12             map.put(num, map.getOrDefault(num, 0) + 1);
13         }
14         List<Integer> list = new ArrayList<>(map.keySet());
15         Collections.sort(list, (a, b) -> Math.abs(a) - Math.abs(b));
16         for (int i = 0; i < list.size(); i++) {
17             int n = list.get(i);
18             if (map.get(n) > map.getOrDefault(2 * n, 0)) {
19                 return false;
20             }
21             map.put(2 * n, map.getOrDefault(2 * n, 0) - map.get(n));
22         }
23         return true;
24     }
25 }

相关题目

954. Array of Doubled Pairs

2007. Find Original Array From Doubled Array

LeetCode 题目总结