还原原数组

难度: Hard

Alice 有一个下标从 0 开始的数组 arr ，由 n 个正整数组成。她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher ：

对每个满足 0 <= i < n 的下标 i ，lower[i] = arr[i] - k
对每个满足 0 <= i < n 的下标 i ，higher[i] = arr[i] + k

不幸地是，Alice 丢失了全部三个数组。但是，她记住了在数组 lower 和 higher 中出现的整数，但不知道每个整数属于哪个数组。请你帮助 Alice 还原原数组。

给你一个由 2n 个整数组成的整数数组 nums ，其中恰好 n 个整数出现在 lower ，剩下的出现在 higher ，还原并返回 原数组 arr 。如果出现答案不唯一的情况，返回任一有效数组。

注意：生成的测试用例保证存在 至少一个 有效数组 arr 。

示例 1：

输入：nums = [2,10,6,4,8,12]
输出：[3,7,11]
解释：
如果 arr = [3,7,11] 且 k = 1 ，那么 lower = [2,6,10] 且 higher = [4,8,12] 。
组合 lower 和 higher 得到 [2,6,10,4,8,12] ，这是 nums 的一个排列。
另一个有效的数组是 arr = [5,7,9] 且 k = 3 。在这种情况下，lower = [2,4,6] 且 higher = [8,10,12] 。

示例 2：

输入：nums = [1,1,3,3]
输出：[2,2]
解释：
如果 arr = [2,2] 且 k = 1 ，那么 lower = [1,1] 且 higher = [3,3] 。
组合 lower 和 higher 得到 [1,1,3,3] ，这是 nums 的一个排列。
注意，数组不能是 [1,3] ，因为在这种情况下，获得 [1,1,3,3] 唯一可行的方案是 k = 0 。
这种方案是无效的，k 必须是一个正整数。

示例 3：

输入：nums = [5,435]
输出：[220]
解释：
唯一可行的组合是 arr = [220] 且 k = 215 。在这种情况下，lower = [5] 且 higher = [435] 。

提示：

2 * n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 10⁹
生成的测试用例保证存在 至少一个 有效数组 arr

Submission

运行时间: 100 ms

内存: 16.5 MB

class Solution:
    def recoverArray(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        for i in range(1, n):
            if nums[i] == nums[i - 1]:
                continue 
            d = nums[i] - nums[0]
            if d & 1: 
                continue 
            k = d // 2
            ans = [] 
            lo, hi = 0, i 
            vis = set() 
            while hi < n:
                while lo in vis: lo += 1 
                while hi < n and nums[hi] - nums[lo] < d: hi += 1 
                if hi == n or nums[hi] - nums[lo] > d: break 
                vis.add(hi)
                ans.append(nums[lo] + k)
                lo += 1
                hi += 1 
            if len(ans) == n // 2:
                return ans 
            


        # cnt1 = Counter(nums)
        # nums1 = list(sorted(set(nums)))
        # for i in range(1, len(nums1)):
        #     k2 = nums1[i] - nums1[0]
        #     if k2 & 1:
        #         continue
        #     vis = set()
        #     ans = []
        #     cnt = Counter(cnt1)
        #     for num in nums1:
        #         if num not in vis:
        #             c = cnt[num + k2]
        #             if c < cnt[num]:
        #                 break
        #             cnt[num + k2] -= cnt[num]
        #             ans.extend([num + k2 // 2] * cnt[num])
        #             if cnt[num + k2] == 0:
        #                 vis.add(num + k2)
        #     else:
        #         return ans

Explain

首先，对输入数组 nums 进行排序。然后遍历数组，尝试找到可能的差值 d = 2k，其中 k 是原数组 arr 和 lower 或 higher 数组之间的差值。这个差值 d 必须是偶数，因为 k 需要是整数。对于每一个可能的 d，尝试将 nums 分为两组，一组表示 lower，一组表示 higher。使用一个集合 vis 来记录已经被使用的 higher 的索引，确保每个元素只被使用一次。通过遍历检查是否可以完全匹配 lower 和 higher 数组。如果成功匹配，说明已经找到了原数组 arr。此算法尝试所有可能的 d，直到找到一个有效的结果。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def recoverArray(self, nums: List[int]) -> List[int]:
        nums.sort()  # 对数组进行排序
        n = len(nums)
        for i in range(1, n):
            if nums[i] == nums[i - 1]:
                continue  # 跳过重复的元素，因为它们不能作为 k 的候选
            d = nums[i] - nums[0]  # 计算可能的差值d
            if d & 1: 
                continue  # 如果 d 不是偶数，则跳过
            k = d // 2  # 计算可能的 k 值
            ans = [] 
            lo, hi = 0, i  # 初始化两个指针
            vis = set()  # 跟踪访问过的 higher 索引
            while hi < n:
                while lo in vis: lo += 1  # 跳过已经访问的 lower 索引
                while hi < n and nums[hi] - nums[lo] < d: hi += 1  # 寻找与 nums[lo] 匹配的 nums[hi]
                if hi == n or nums[hi] - nums[lo] > d: break  # 如果没有找到匹配，或者差值过大，中断循环
                vis.add(hi)  # 标记此 higher 索引为已访问
                ans.append(nums[lo] + k)  # 将计算得到的 arr 元素加入结果列表
                lo += 1
                hi += 1 
            if len(ans) == n // 2:
                return ans  # 如果找到完整的解，返回结果

Explore

在这个问题中，我们需要将数组 nums 分解为两组 lower 和 higher，其中 higher 中的每一个元素都比对应的 lower 中的元素大 d，且这个差值 d 等于 2k。因此，为了使 k 为一个整数，d 必须是偶数。这是因为任何偶数除以 2 的结果都是整数，而如果 d 是奇数，则 d/2 会得到一个分数，不符合 k 为整数的要求。

在这种方法中，跳过重复元素是为了防止重复计算相同的差值 d。如果数组中有重复的元素，计算的差值 d 会相同，从而导致算法重复检查相同的 k 值，这样会降低算法效率。此外，重复的元素可能不适合作为分组的起始点，因为它们不会引入新的差值 d，从而可能错过探索新的分组方式。

选择 nums[i] - nums[0] 作为起始的差值 d 是基于将数组的最小元素作为lower组的起始点，这样可以简化问题的复杂度。通过这种方式，我们可以从最小可能的差值开始探索，逐步增大差值，直到找到合适的 k 值。这种方法能够系统地覆盖所有可能的差值，并确保不遗漏任何可能的 k 值。

当 nums[hi] - nums[lo] > d 时中断循环是基于这样的假设：已经对 nums 进行了排序，如果在当前 lower 索引 lo 的情况下，没有在 higher 找到匹配的元素，而是找到了一个差值大于 d 的元素，那么对于当前的 d 和 k，正确的分组已经不可能实现。因为随着 lo 的增加，lower 的值会增大，从而使得满足 nums[hi] - nums[lo] = d 的 hi 的值也应该相应地更大或无法找到，因此不会漏掉正确的 k 值。