https://leetcode.com/problems/array-of-doubled-pairs/
https://blog.csdn.net/fuxuemingzhu/article/details/84925747
题目的意思是奇数位置的数字能不能安排成它左边的那个位置的二倍。
使用的方法是统计次数、然后遍历查找的方式，和Two Sum之类的很类似。需要注意的是，我们对数组进行了排序，这样保证下面的遍历是从小到大开始的。另外，由于排序之后，对于负数而言，小数字是大数字的2倍，所以，需要做一个正负的判断。
对于负数来说，我们找出它的1/2是不是在数组中；对于正数来说，我们找出它的2倍是不是在数组中。如果找到了要找的数字之后，把它的次数减去当前的数字的次数，以方便后面的统计。所以，如果所有的数字都满足条件的话，那么就一波一波的都消除掉了。
https://leetcode.com/articles/array-of-doubled-pairs/
https://leetcode.com/problems/array-of-doubled-pairs/discuss/203183/JavaC%2B%2BPython-Match-from-the-Smallest-or-Biggest-100
https://zhanghuimeng.github.io/post/leetcode-954-array-of-doubled-pairs/
https://leetcode.com/problems/array-of-doubled-pairs/discuss/203308/Java-Solution-one-hashmap-only-(for-both-positive-and-negative-numbers)-!
// (0). one map only: to count the frequency of apperance of each number
// (1). Sort the array, then scan from the smalllest to find (x, 2x) pairs
// ___ (a) for negative number, we will see 2x first, the match should be half of it.
// ___ (b). for positive, we will see x first, the match should be two times of it.
// (2) once matched, update the map
// (3). no need to put 0 into the map.
Example: [3, 6, -4, -2, 0, 0, 14, 7, -2, -4]
Your stdout
map: {-2=2, -4=2, 3=1, 6=1, 7=1, 14=1}
map: {-2=0, -4=0, 3=1, 6=1, 7=1, 14=1} after process (-4, -2) pair
map: {-2=0, -4=0, 3=0, 6=0, 7=1, 14=1} after process (3, 6) pair
map: {-2=0, -4=0, 3=0, 6=0, 7=0, 14=0} after process (7, 14) pair
https://leetcode.com/problems/array-of-doubled-pairs/discuss/203191/JAVA-17ms-O(200000)-without-Sorting-but-with-Explanation
Given an array of integers
A with even length, return true if and only if it is possible to reorder it such that A[2 * i + 1] = 2 * A[2 * i] for every 0 <= i < len(A) / 2.
Example 1:
Input: [3,1,3,6] Output: false
Example 2:
Input: [2,1,2,6] Output: false
Example 3:
Input: [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: [1,2,4,16,8,4] Output: false
Note:
0 <= A.length <= 30000A.lengthis even-100000 <= A[i] <= 100000
https://blog.csdn.net/fuxuemingzhu/article/details/84925747
题目的意思是奇数位置的数字能不能安排成它左边的那个位置的二倍。
使用的方法是统计次数、然后遍历查找的方式，和Two Sum之类的很类似。需要注意的是，我们对数组进行了排序，这样保证下面的遍历是从小到大开始的。另外，由于排序之后，对于负数而言，小数字是大数字的2倍，所以，需要做一个正负的判断。
对于负数来说，我们找出它的1/2是不是在数组中；对于正数来说，我们找出它的2倍是不是在数组中。如果找到了要找的数字之后，把它的次数减去当前的数字的次数，以方便后面的统计。所以，如果所有的数字都满足条件的话，那么就一波一波的都消除掉了。
https://leetcode.com/articles/array-of-doubled-pairs/
If
x is currently the array element with the least absolute value, it must pair with 2*x, as there does not exist any other x/2 to pair with it.
Algorithm
Let's try to (virtually) "write" the final reordered array.
Let's check elements in order of absolute value. When we check an element
x and it isn't used, it must pair with 2*x. We will attempt to write x, 2x - if we can't, then the answer is false. If we write everything, the answer is true.
To keep track of what we have not yet written, we will store it in a
count.
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;
}
https://leetcode.com/problems/array-of-doubled-pairs/discuss/203183/JavaC%2B%2BPython-Match-from-the-Smallest-or-Biggest-100
Assume all interger are positive, for example
We have one
Then one
We need to match it with one
Finaly no number left.
[2,4,4,8].We have one
x = 2, we need to match it with one 2x = 4.Then one
4 is gone, we have the other x = 4.We need to match it with one
2x = 8.Finaly no number left.
Why we start from
Because it's the smallest and we no there is no
So we know we need to find
2?Because it's the smallest and we no there is no
x/2 left.So we know we need to find
2x
What if the case negative?
One way is that start from the biggest (with abosolute value smallest),
and we aplly same logic.
One way is that start from the biggest (with abosolute value smallest),
and we aplly same logic.
Another way is that start from the smallest (with abosolute value biggest),
and we try to find
and we try to find
x/2 each turn.Explanation
- Count all numbers.
- Loop all numbers on the order of its absolute.
We havecounter[x]ofx, so we need the same amount of2xwo match them.
Ifc[x] > c[2 * x], then we return false
Ifc[x] <= c[2 * x], then we doc[2 * x] -= c[x]to remove matched2x.
Don't worry about
0, it doesn't fit the logic above but it won't break our algorithme.
In case count[0] is odd, it won't get matched in the end.
(Anyway you can return false earlier here)
(Anyway you can return false earlier here)
In case count[0] is even, we still have
And we still need to check all other numbers.
c[0] <= c[2 * 0].And we still need to check all other numbers.
public boolean canReorderDoubled(int[] A) {
Map<Integer, Integer> count = new TreeMap<>();
for (int a : A)
count.put(a, count.getOrDefault(a, 0) + 1);
for (int x : count.keySet()) {
if (count.get(x) == 0) continue;
int want = x < 0 ? x / 2 : x * 2;
if (x < 0 && x % 2 != 0 || count.get(x) > count.getOrDefault(want, 0))
return false;
count.put(want, count.get(want) - count.get(x));
}
return true;
}
If the input array is not sorted, then it is difficult to know for A[2 * i], whether it should be used to match A[2 * i + 1] = 2 * A[2 * i] or A[2 * i] = 2 * A[2 * i - 1]. But if we sort the input array, it makes this matching process easier as shown in the following.
For all the sorted negative integers, start to match from smallest to largest; (-4 < -2)
For all the sorted positive integers, start to match from smallest to largest; (2 < 4)
When following the above match order, we know that in order to be able to make this array a complete doubled pairs, if there are m of integer a, then there must be at least m of integer 2 * a(for a >= 0) or a /2 (for a < 0).
As a result, we need a fast way to keep all the counts of unused integers, a hint for hash map. The keys would be all the integers and the values are the frequencies of these integers. Combined with the need of having all integers in sorted order, we use TreeMap.
The runtime is O(N * logN), constructing the tree map is the dominant part of the runtime.
X. https://www.acwing.com/solution/leetcode/content/686/https://zhanghuimeng.github.io/post/leetcode-954-array-of-doubled-pairs/
这道题用贪心就可以解决。对于当前还剩的绝对值最小的数，它必然需要和它的两倍的数配对；最后所有的数都需要配对完。以及0只能自己和自己配对，所以0的总数应该是偶数。
bool canReorderDoubled(vector<int>& A) { int positive[100001], negative[100001]; memset(positive, 0, sizeof(positive)); memset(negative, 0, sizeof(negative)); for (int x: A) { if (x >= 0) positive[x]++; else negative[-x]++; } if (positive[0] % 2 != 0) return false; for (int i = 1; i <= 100000; i++) { if (positive[i] != 0) { if (i > 50000 || positive[i*2] < positive[i]) return false; positive[i*2] -= positive[i]; } } for (int i = 1; i <= 100000; i++) { if (negative[i] != 0) { if (i > 50000 || negative[i*2] < negative[i]) return false; negative[i*2] -= negative[i]; } } return true; }
https://leetcode.com/problems/array-of-doubled-pairs/discuss/203308/Java-Solution-one-hashmap-only-(for-both-positive-and-negative-numbers)-!
// (0). one map only: to count the frequency of apperance of each number
// (1). Sort the array, then scan from the smalllest to find (x, 2x) pairs
// ___ (a) for negative number, we will see 2x first, the match should be half of it.
// ___ (b). for positive, we will see x first, the match should be two times of it.
// (2) once matched, update the map
// (3). no need to put 0 into the map.
Example: [3, 6, -4, -2, 0, 0, 14, 7, -2, -4]
Your stdout
map: {-2=2, -4=2, 3=1, 6=1, 7=1, 14=1}
map: {-2=0, -4=0, 3=1, 6=1, 7=1, 14=1} after process (-4, -2) pair
map: {-2=0, -4=0, 3=0, 6=0, 7=1, 14=1} after process (3, 6) pair
map: {-2=0, -4=0, 3=0, 6=0, 7=0, 14=0} after process (7, 14) pair
public boolean canReorderDoubled(int[] A) {
int n = A.length;
if (n % 2 != 0) return false;
Arrays.sort(A);
Map<Integer, Integer> map = new HashMap<>(); // <num, freq>
for (int item : A) {
if (item == 0) continue;
map.put(item, map.getOrDefault(item, 0) + 1);
}
for (int i = 0; i < n; i++) {
if (A[i] != 0 && map.get(A[i]) > 0) {
//System.out.println("map: " + map);
int target = A[i] * 2; // (3). positive, target = 2x
if (A[i] < 0) { // (2) for negative (-4), the match should be half of it.
if (A[i] % 2 != 0) { // A[i] = -7, A[i] / 2 = -3
return false;
} else {
target = A[i] / 2; // negative: target = x
}
}
if (map.getOrDefault(target, 0) < map.get(A[i])) {
return false;
} else {
// (4) once matched, update the map
map.put(target, map.get(target) - map.get(A[i]));
map.put(A[i], 0);
}
}
}
//System.out.println("map: " + map);
return true;
}
https://leetcode.com/problems/array-of-doubled-pairs/discuss/203191/JAVA-17ms-O(200000)-without-Sorting-but-with-Explanation
map.put(item, map.getOrDefault(item, 0) + 1); you could simply write map.merge(item, 1, Integer::sum);?