跳转至

954.array-of-doubled-pairs

Statement

Metadata

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。

 

示例 1：

输入：arr = [3,1,3,6]
输出：false

示例 2：

输入：arr = [2,1,2,6]
输出：false

示例 3：

输入：arr = [4,-2,2,-4]
输出：true
解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]

 

提示：

  • 0 <= arr.length <= 3 * 104
  • arr.length 是偶数
  • -105 <= arr[i] <= 105

Metadata

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

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T& a, const S& b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T& a, const S& b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        auto check = [&arr](int f) {
            map<int, int> mp;
            for (const auto& a : arr) {
                if (a == 0) {
                    ++mp[a];
                    continue;
                }

                if (a * f > 0) {
                    ++mp[a * f];
                }
            }

            for (const auto& [k, v] : mp) {
                if (v == 0) {
                    continue;
                }

                if (k == 0) {
                    if (v & 1) {
                        return false;
                    }
                    continue;
                }

                if (mp[k * 2] < v) {
                    return false;
                }

                mp[k * 2] -= v;
            }

            return true;
        };

        return check(1) && check(-1);
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif
最后更新: October 11, 2023
回到页面顶部