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:

  1. 0 <= A.length <= 30000
  2. A.length is even
  3. -100000 <= A[i] <= 100000

Idea 1. Kind of counting sort + hashMap

Time complexity: O(n + m) where m = max(A), n = A.length

Space complexity: O(m)

 class Solution {
public boolean canReorderDoubled(int[] A) {
int n = 20000;
int[] negatives = new int[n+1];
int[] positives = new int[n+1]; for(int a: A) {
if(a < 0) {
++negatives[-a];
}
else {
++positives[a];
}
} for(int i = 0; i <= n; ++i) {
if(negatives[i] != 0) {
if(negatives[2*i] < negatives[i]) {
return false;
}
else {
negatives[2*i] -= negatives[i];
}
} if(positives[i] != 0) {
if(positives[2*i] < positives[i]) {
return false;
}
else {
positives[2*i] -= positives[i];
}
}
} return true;
}
}

Idea 1.a TreeMap + absoluate value as comparator, no need to deal with /2 for negative values

Time complexity: O(nlogn)

Space complexity: O(n)

 class Solution {
public boolean canReorderDoubled(int[] A) {
Comparator<Integer> comparator = (Integer a, Integer b) -> {
int absEqual = Integer.compare(Math.abs(a), Math.abs(b));
if(absEqual == 0 && a != b) {
return Integer.compare(a, b);
}
return absEqual;
}; Map<Integer, Integer> count = new TreeMap<>(comparator); for(int a : A) {
count.put(a, count.getOrDefault(a, 0) + 1);
} for(int key: count.keySet()) {
int want = count.getOrDefault(2*key, 0);
if(count.get(key) > want) {
return false;
}
else if(count.containsKey(2*key)) {
count.put(2*key, want - count.get(key));
}
} return true;
}
}

Idea1.c normal treeMap with both positive + negatives

 class Solution {
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 key: count.keySet()) {
if(count.get(key) == 0) {
continue;
} int next = key < 0? key/2 : key*2;
int want = count.getOrDefault(next, 0);
if(count.get(key) > want) {
return false;
} count.put(next, want - count.get(key)); } return true;
}
}
05-11 18:12
查看更多