陕西咸阳做网站的公司有哪些,0511网站,做网站一天忙吗,微信咋做自己的网站文章目录1. 题目2. 解题1. 题目
一个整数数组 original 可以转变成一个 双倍 数组 changed #xff0c;转变方式为将 original 中每个元素 值乘以 2 加入数组中#xff0c;然后将所有元素 随机打乱 。
给你一个数组 changed #xff0c;如果 change 是 双倍 数组#xff…
文章目录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:vectorint findOriginalArray(vectorint changed) {if(changed.size()%21) return {};mapint,int m;for(auto n : changed)m[n];vectorint 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阿明一起加油、一起学习进步
