class Solution {
public:
vector<int> findOriginalArray(vector<int>& changed) {
}
};
2007. 从双倍数组中还原原数组
一个整数数组 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 <= 1050 <= changed[i] <= 105原站题解
javascript 解法, 执行用时: 281 ms, 内存消耗: 79.4 MB, 提交时间: 2024-04-18 14:19:30
/**
* @param {number[]} changed
* @return {number[]}
*/
var findOriginalArray = function(changed) {
changed.sort((a, b) => a - b);
const ans = [];
const q = Array(changed.length);
let front = 0, rear = 0;
for (const x of changed) {
if (front < rear) {
if (q[front] < x) { // 无法配对
return [];
}
if (q[front] === x) { // 配对成功
front++; // 清除一个标记
continue;
}
}
ans.push(x);
q[rear++] = x * 2; // 添加双倍标记
}
// 只有所有双倍标记都被清除掉，才能说明 changed 是一个双倍数组
return front < rear ? [] : ans;
};
rust 解法, 执行用时: 45 ms, 内存消耗: 4.5 MB, 提交时间: 2024-04-18 14:18:38
use std::collections::HashMap;
impl Solution {
pub fn find_original_array(changed: Vec<i32>) -> Vec<i32> {
let mut cnt = HashMap::new();
for &x in &changed {
*cnt.entry(x).or_insert(0) += 1;
}
// 单独处理 0
let cnt0 = cnt.remove(&0).or(Some(0)).unwrap();
if cnt0 % 2 != 0 {
return vec![];
}
let mut ans = vec![0; (cnt0 / 2) as usize];
for x in cnt.keys().map(|&k| k).collect::<Vec<_>>() {
// 如果 x/2 在 cnt 中，则跳过
if x % 2 == 0 && cnt.contains_key(&(x / 2)) {
continue;
}
// 把 x, 2x, 4x, 8x, ... 全部配对
let mut x = x;
while let Some(&cnt_x) = cnt.get(&x) {
// 每次循环，把 cnt_x 个 x 和 cnt_x 个 2x 配对
let cnt_2x = cnt.get_mut(&(x * 2));
// 有 x 没有 2x，无法配对
if cnt_2x.is_none() {
return vec![];
}
let cnt_2x = cnt_2x.unwrap();
// 无法配对，至少要有 cnt_x 个 2x
if cnt_x > *cnt_2x {
return vec![];
}
ans.extend(std::iter::repeat(x).take(cnt_x as usize));
if cnt_x < *cnt_2x {
// 还剩下一些 2x
*cnt_2x -= cnt_x;
x *= 2;
} else {
x *= 4;
}
}
}
ans
}
}
golang 解法, 执行用时: 157 ms, 内存消耗: 12 MB, 提交时间: 2024-04-18 14:18:24
func findOriginalArray(changed []int) []int {
cnt := map[int]int{}
for _, x := range changed {
cnt[x]++
}
// 单独处理 0
cnt0 := cnt[0]
if cnt0%2 == 1 {
return nil
}
delete(cnt, 0)
ans := make([]int, cnt0/2, len(changed)/2)
for x := range cnt {
// 如果 x/2 在 cnt 中，则跳过
if x%2 == 0 && cnt[x/2] > 0 {
continue
}
// 把 x, 2x, 4x, 8x, ... 全部配对
for cnt[x] > 0 {
// 每次循环，把 cntX 个 x 和 cntX 个 2x 配对
cntX := cnt[x]
// 无法配对，至少要有 cntX 个 2x
if cntX > cnt[x*2] {
return nil
}
for i := 0; i < cntX; i++ {
ans = append(ans, x)
}
if cntX < cnt[x*2] {
// 还剩下一些 2x
cnt[x*2] -= cntX
x *= 2
} else {
x *= 4
}
}
}
return ans
}
python3 解法, 执行用时: 150 ms, 内存消耗: 32.7 MB, 提交时间: 2024-04-18 14:17:23
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
cnt = Counter(changed)
# 单独处理 0
cnt0 = cnt.pop(0, 0)
if cnt0 % 2:
return []
ans = [0] * (cnt0 // 2)
for x in cnt:
# 如果 x/2 在 cnt 中，则跳过
if x % 2 == 0 and x // 2 in cnt:
continue
# 把 x, 2x, 4x, 8x, ... 全部配对
while x in cnt:
# 每次循环，把 cnt_x 个 x 和 cnt_x 个 2x 配对
cnt_x = cnt[x]
# 无法配对，至少要有 cnt_x 个 2x
if cnt_x > cnt[x * 2]:
return []
ans.extend([x] * cnt_x)
if cnt_x < cnt[x * 2]:
# 还剩下一些 2x
cnt[x * 2] -= cnt_x
x *= 2
else:
x *= 4
return ans
def findOriginalArray2(self, changed: List[int]) -> List[int]:
changed.sort()
ans = []
q = deque()
for x in changed:
if q:
if q[0] < x: # 无法配对
return []
if q[0] == x: # 配对成功
q.popleft() # 清除一个标记
continue
ans.append(x)
q.append(x * 2) # 添加双倍标记
# 只有所有双倍标记都被清除掉，才能说明 changed 是一个双倍数组
return [] if q else ans
java 解法, 执行用时: 57 ms, 内存消耗: 60.4 MB, 提交时间: 2023-09-17 11:50:45
class Solution {
public int[] findOriginalArray(int[] changed) {
int n = changed.length;
// n必须是偶数
if (n % 2 != 0) {
return new int[0];
}
// 排序以按序匹配元素
Arrays.sort(changed);
Queue<Integer> queue = new LinkedList<>();
int[] ans = new int[n / 2];
int t = 0;
for (int i = 0; i < n; i++) {
// 待匹配元素已得到匹配
if (!queue.isEmpty() && queue.peek() == changed[i]) {
ans[t++] = queue.poll() / 2;
} else {
// changed[i]作为原数组元素，changed[i] * 2作为需要被匹配元素放入队列中
queue.offer(changed[i] * 2);
}
}
// 这里写queue.isEmpty()或者t==n/2都可以，都表示已得到一个可能的原数组
if (queue.isEmpty()) {
return ans;
}
return new int[0];
}
// 双指针
public int[] findOriginalArray2(int[] changed) {
int n = changed.length;
// n必须是偶数
if (n % 2 != 0) {
return new int[0];
}
// 排序以按序匹配元素
Arrays.sort(changed);
Queue<Integer> queue = new LinkedList<>();
// 记录已经匹配的元素
boolean[] vis = new boolean[n];
int[] ans = new int[n / 2];
int t = 0;
int left = 0;
int right = 1;
for (int i = 0; i < n / 2; i++) {
// 找到一个原数组元素
while (vis[left]) {
left++;
}
// 这里主要是为了处理为0的情况
if (right == left) {
right = left + 1;
}
// 找到对应的一个二倍数组元素
while (right < n && changed[left] * 2 != changed[right]) {
right++;
}
// 未找到直接退出
if (right == n) {
break;
}
vis[right] = true;
ans[t++] = changed[left];
left++;
right++;
}
if (t == n / 2) {
return ans;
}
return new int[0];
}
}
python3 解法, 执行用时: 296 ms, 内存消耗: 32.5 MB, 提交时间: 2023-09-17 11:49:57
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
changed.sort()
res, cnts = [], collections.Counter(changed)
for x in changed:
if cnts[x] > 0:
# 注意只有当计数仍大于0的话才判断, 否则说明已经被作为一个2倍数字用掉了
if cnts[2 * x] <= 0 or x == 0 and cnts[x] < 2:
# 如果二倍数字不存在, 或者当前数字是0且计数小于2, 肯定不可能是双倍数组
return []
# x属于原数组
res.append(x)
cnts[x] -= 1
cnts[2 * x] -= 1
return res
cpp 解法, 执行用时: 248 ms, 内存消耗: 119.1 MB, 提交时间: 2023-09-17 11:49:41
/**
* 小的值优先匹配小的，所以先用sort进行排序 然后可以将暂时没匹配到的数字存放至队列中，
* 使用队列也是为了优先匹配小的，小的先进，小的先出。
* 每次等到匹配到的时候，就将队列中的数取出。最后判断队列是否为空。
*/
class Solution {
public:
vector<int> findOriginalArray(vector<int>& changed) {
sort(changed.begin(),changed.end());
queue<int> q;
vector<int> res,empty;
int n = changed.size();
if(n%2)return empty;
for(int i=0;i<n;i++){
if(q.empty())
q.push(changed[i]);
else{
if(q.front()*2 == changed[i]){
res.push_back(q.front());
q.pop();
}
else
q.push(changed[i]);
}
}
if(!q.empty())
return empty;
return res;
}
};
cpp 解法, 执行用时: 448 ms, 内存消耗: 142.2 MB, 提交时间: 2023-09-17 11:48:50
class Solution {
public:
vector<int> findOriginalArray(vector<int> &changed) {
int n = changed.size();
if (n % 2 != 0) return {};
sort(changed.begin(), changed.end());
map<int, int> mp;
for (int i: changed) ++mp[i];
vector<int> ans;
int cnt = 0;
for (int i: changed) {
if (mp[i] == 0) continue;
if (mp.count(i * 2) && mp[i * 2] != 0) {
ans.emplace_back(i);
--mp[i];
--mp[i * 2];
cnt += 2;
} else return {};
}
return cnt == n ? ans : vector<int>{};
}
};
golang 解法, 执行用时: 296 ms, 内存消耗: 10 MB, 提交时间: 2023-09-17 11:48:17
func findOriginalArray(changed []int) (original []int) {
sort.Ints(changed)
cnt := map[int]int{}
for _, v := range changed {
if cnt[v] == 0 { // v 不是双倍后的元素
cnt[v*2]++ // 标记一个双倍元素
original = append(original, v)
} else {
cnt[v]-- // 清除一个标记
if cnt[v] == 0 {
delete(cnt, v)
}
}
}
// 只有当所有双倍标记都被清除掉时，才能说明 changed 是一个双倍数组
if len(cnt) == 0 {
return
}
return nil
}