Skip to content

Latest commit

 

History

History
153 lines (103 loc) · 5.38 KB

2007.find-original-array-from-doubled-array.md

File metadata and controls

153 lines (103 loc) · 5.38 KB

题目地址(2007. 从双倍数组中还原原数组)

https://leetcode-cn.com/problems/find-original-array-from-doubled-array/

题目描述

一个整数数组 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 <= 105
0 <= changed[i] <= 105

前置知识

  • 哈希表

公司

  • 暂无

思路

由于 0 乘以 2 等于自身,因此这种情况比较特殊,我们先考虑其他一般情况,最后再加 0 这个特判。

由于 changed 中的最小值一定是原数组中的最小值,同理 changed 中的最大值是原数组中的最大值乘以 2.因此实际上,我们可以确定性得出原数组的两个数了。

那么剩下的数呢?我们可以利用贪心消除法来解决。

即先对 changed 进行排序,并从小到大进行处理。对于 1 <= i <= n - 2, changed[i] 其可能是原数组中的值,也可能是原数组 double 后的值。但是如果其 2 * changes[i] 存在于 changed 中,那么其一定是原数组中的值。

这个结论成立的前提是后面讲的 "遇到这样的匹配我们就将匹配的双方消除"。 试想如果基于这种消除的思想这个结论不成立,那么 changes[i] 一定不会被消除,而只要有一个无法被消除,就是无解的。

这样我们就找到了一对 (changed[i], 2 * changed[i]),将 changes[i] 加入 ans,并将 2 * changed[i] 从 changed 中移除。

算法:

  • 对 changed 进行排序,这样从左到右遍历的时候,我们可以确保枚举到的是原数组中的项(成立的前提依旧是上面提到的消除)
  • 遍历 changed。 如果 changed[i] * 2 存在且可以和 changed[i] 消除(个数足够,换句话说就是 changed[i] 数目不大于 changed[i]*2 的数目),则进行消除。

如果最后 ans 长度是 changed 一半,说明我们找到了答案,返回即可。否则返回空数组。

关键点

  • 对 changed 进行排序后再处理

代码

  • 语言支持:Python3

Python3 Code:

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        counter = collections.Counter(changed)
        if counter[0] % 2: return []
        n = len(changed)
        changed.sort()
        ans = []
        for c in changed:
            if counter[c] < 1: continue
            double = c * 2
            if double in counter:
                ans.append(c)
            else:
                return []
            if double == 0:
                counter[double] -= 2
            else:
                counter[double] -= 1
                counter[c] -= 1
        if len(ans) == n // 2: return ans
        return []

复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$

相关题目

  • 5966. 还原原数组 2007 和这道题思路类似,都是消除思想。这道题的难点在于 k 是未知的,我们需要先枚举出 k,然后再利用消除思想解决。参考代码:
class Solution:
    def recoverArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        nums.sort()
        for i in range(n):
            # enumerate i, assueme that: nums[i] is higher[0]
            d = nums[i] - nums[0]
            if d == 0 or d & 1: continue # k 应该是大于 0 的整数
            k = d // 2
            counter = collections.Counter(nums)
            ans = []
            for key in sorted(counter):
                if counter[key + 2 * k] >= counter[key]:
                    ans += [key + k] * counter[key]
                    counter[key + 2 * k] -= counter[key]
                else:
                    break # 剪枝(不剪枝的话实测 Python 也能通过,不过要多花很多时间)
            if len(ans) == n // 2: return ans
        return []

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。