2122.还原原数组

链接：2122.还原原数组
难度：Hard
标签：数组、哈希表、枚举、排序
简介：给你一个由 2n 个整数组成的整数数组 nums ，其中 恰好 n 个整数出现在 lower ，剩下的出现在 higher ，还原并返回 原数组 arr 。如果出现答案不唯一的情况，返回 任一 有效数组。

题解 1 - cpp

• 编辑时间：2021-12-31
• 执行用时：880ms
• 内存消耗：285.8MB
• 编程语言：cpp
• 解法介绍：存入 map 分别统计。

class Solution {
   public:
    int get_k(unordered_map<int, int> m, vector<int>& nums, int k,
              vector<int>& ans) {
        for (int i = 0; i < nums.size(); i++) {
            int low = nums[i];
            if (m.count(low) == 0 || m[low] <= 0) continue;
            int high = low + 2 * k;
            if (m.count(high) == 0 || m[high] <= 0) return 0;
            m[low]--;
            m[high]--;
            ans.push_back(low + k);
        }
        return k;
    }
    vector<int> recoverArray(vector<int>& nums) {
        unordered_map<int, int> m;
        for (auto& num : nums) m[num]++;
        sort(nums.begin(), nums.end());
        vector<int> ans;
        int v1 = nums[0], v2, k = 0;
        for (int i = 1; i < nums.size() && k == 0; i++) {
            ans.clear();
            v2 = nums[i];
            if ((v2 - v1) & 1 || (v2 - v1) <= 1) continue;
            k = get_k(m, nums, (v2 - v1) / 2, ans);
        }
        return ans;
    }
};