LeetCode 5860. 從雙倍數組中還原原數組(map)

Michael阿明 2021-09-19 16:23:29 阅读数:697

leetcode map

文章目錄

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;
}
else
return {
};
}
return ans;
}
};

400 ms 140.6 MB C++


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

長按或掃碼關注我的公眾號(Michael阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210919162329100T.html