文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

一個整數數組 original 可以轉變成一個 雙倍 數組 changed ，轉變方式為將 original 中每個元素 值乘以 2 加入數組中，然后將所有元素 隨機打亂 。

給你一個數組 changed ，如果 change 是 雙倍 數組，那么請你返回 original數組，否則請返回空數組。original 的元素可以以 任意 順序返回。

示例 1： 輸入：changed = [1,3,4,2,6,8] 輸出：[1,3,4] 解釋：一個可能的 original 數組為 [1,3,4] : - 將 1 乘以 2 ，得到 1 * 2 = 2 。 - 將 3 乘以 2 ，得到 3 * 2 = 6 。 - 將 4 乘以 2 ，得到 4 * 2 = 8 。 其他可能的原數組方案為 [4,3,1] 或者 [3,1,4] 。示例 2： 輸入：changed = [6,3,0,1] 輸出：[] 解釋：changed 不是一個雙倍數組。示例 3： 輸入：changed = [1] 輸出：[] 解釋：changed 不是一個雙倍數組。提示： 1 <= changed.length <= 10^5 0 <= changed[i] <= 10^5

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-original-array-from-doubled-array
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 數組長度需要為偶數
• map計數，map有序，每次取出 begin 的數值 x，查找是否存在 2*x，計數為0時，刪除元素

class Solution { public:vector<int> findOriginalArray(vector<int>& changed) {if(changed.size()%2==1) return {};map<int,int> m;for(auto n : changed)m[n]++;vector<int> ans(changed.size()/2);int i = 0;while(!m.empty()){int x = m.begin()->first;if(--m[x] == 0)m.erase(x);if(m.find(2*x) != m.end()){if(--m[2*x] == 0)m.erase(2*x);ans[i++] = x;}elsereturn {};}return ans;} };

400 ms 140.6 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 2007. 从双倍数组中还原原数组（map）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。