Problem
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
Solution 1:
Time complexity: O(N + 100000 * 2)
Space complexity: O(100000 * 2)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua, 108 ms class Solution { public: bool canReorderDoubled(vector<int>& A) { const int kMaxN = 100000; vector<int> p(kMaxN + 1); vector<int> n(kMaxN + 1); for (int a : A) { if (a >= 0) ++p[a]; else ++n[-a]; } for (int i = 0; i <= kMaxN / 2; ++i) { if (p[i] && (p[i * 2] -= p[i]) < 0) return false; if (n[i] && (n[i * 2] -= n[i]) < 0) return false; } return true; } }; |
Solution 2:
Time complexity: O(NlogN)
Space complexity: O(N)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua, 108 ms class Solution { public: bool canReorderDoubled(vector<int>& A) { unordered_map<int, int> c; for (int a : A) ++c[a]; vector<int> keys; for (const auto &kv : c) keys.push_back(kv.first); sort(begin(keys), end(keys), [](int a, int b) { return abs(a) < abs(b); }); for (int key : keys) if (c[key] && (c[key * 2] -= c[key]) < 0) return false; return true; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment