Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/954.html
954. Array of Doubled Pairs (Medium)
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 <= 30000
A.length
is even-100000 <= A[i] <= 100000
Companies:
Google
Related Topics:
Array, Hash Table
Solution 1. Greedy
// OJ: https://leetcode.com/problems/array-of-doubled-pairs/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
bool canReorderDoubled(vector<int>& A) {
multiset<int> s(A.begin(), A.end());
while (s.size()) {
int val = *s.begin();
if (val < 0 && val % 2) return false;
int next = val >= 0 ? val * 2 : val / 2;
s.erase(s.begin());
auto it = s.find(next);
if (it == s.end()) return false;
s.erase(it);
}
return true;
}
};
-
class Solution { public boolean canReorderDoubled(int[] A) { List<Integer> list = new ArrayList<Integer>(); int length = A.length; for (int i = 0; i < length; i++) list.add(A[i]); Collections.sort(list, new Comparator<Integer>() { public int compare(Integer num1, Integer num2) { if (Math.abs(num1) != Math.abs(num2)) return Math.abs(num1) - Math.abs(num2); else return num1 - num2; } }); while (list.size() > 0) { int num = list.remove(0); int num2 = num * 2; int index = list.indexOf(num2); if (index >= 0) list.remove(index); else return false; } return true; } } ############ class Solution { public boolean canReorderDoubled(int[] arr) { Map<Integer, Integer> freq = new HashMap<>(); for (int v : arr) { freq.put(v, freq.getOrDefault(v, 0) + 1); } if ((freq.getOrDefault(0, 0) & 1) != 0) { return false; } List<Integer> keys = new ArrayList<>(freq.keySet()); keys.sort(Comparator.comparingInt(Math::abs)); for (int k : keys) { if (freq.getOrDefault(k << 1, 0) < freq.get(k)) { return false; } freq.put(k << 1, freq.getOrDefault(k << 1, 0) - freq.get(k)); } return true; } }
-
// OJ: https://leetcode.com/problems/array-of-doubled-pairs/ // Time: O(NlogN) // Space: O(N) class Solution { public: bool canReorderDoubled(vector<int>& A) { multiset<int> s(A.begin(), A.end()); while (s.size()) { int val = *s.begin(); if (val < 0 && val % 2) return false; int next = val >= 0 ? val * 2 : val / 2; s.erase(s.begin()); auto it = s.find(next); if (it == s.end()) return false; s.erase(it); } return true; } };
-
class Solution: def canReorderDoubled(self, arr: List[int]) -> bool: freq = Counter(arr) if freq[0] & 1: return False for x in sorted(freq, key=abs): if freq[x << 1] < freq[x]: return False freq[x << 1] -= freq[x] return True ############ class Solution(object): def canReorderDoubled(self, A): """ :type A: List[int] :rtype: bool """ A.sort() N = len(A) count = collections.Counter(A) for i in range(N): if A[i] == 0 or A[i] not in count: continue elif A[i] < 0: if A[i] % 2 == 1 or count[A[i] / 2] == 0: return False else: count[A[i] / 2] -= count[A[i]] if count[A[i] / 2] == 0: del count[A[i] / 2] del count[A[i]] else: if count[A[i] * 2] == 0: return False else: count[A[i] * 2] -= count[A[i]] if count[A[i] * 2] == 0: del count[A[i] * 2] del count[A[i]] return True
-
func canReorderDoubled(arr []int) bool { freq := make(map[int]int) for _, v := range arr { freq[v]++ } if freq[0]%2 != 0 { return false } var keys []int for k := range freq { keys = append(keys, k) } sort.Slice(keys, func(i, j int) bool { return abs(keys[i]) < abs(keys[j]) }) for _, k := range keys { if freq[k*2] < freq[k] { return false } freq[k*2] -= freq[k] } return true } func abs(x int) int { if x < 0 { return -x } return x }