2122-还原原数组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:15:46 2023-09-13 16:15:46 Updated    

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

  1. 对每个满足 0 <= i < n 的下标 i ，lower[i] = arr[i] - k
  2. 对每个满足 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] <= 109
  • 生成的测试用例保证存在 至少一个 有效数组 arr

方法一：枚举 + 双指针

思路与算法

我们首先将数组 arr 按照升序排序。

根据题目的要求，arr 可以拆分成两个长度为 n 的数组，并且对于元素较小的那个数组 lower 中的每一个元素，在元素较大的那个数组 upper 中都唯一对应着一个恰好比它大 2k 的元素。当 arr 有序时，最小的那个元素 arr}[0] 一定是属于 lower 的，这样一来，我们就可以枚举 arr 中剩余的 2n-1 个元素，分别作为 arr}[0] 在 upper 中唯一对应的元素，并判断剩余元素的合法性。

假设 arr}[0] 对应着 arr}[i]，那么我们就可以得到 k 的值：

k = arr[i] - arr[0]}{2}

由于 k 是整数并且 k > 0，因此我们必须要求 arr}[0] 与 arr}[i] 同奇偶，并且它们的值不相等。在求出 k 的值后，我们可以使用双指针的方法判断剩余的元素是否满足要求：

  • 我们用两个指针 left 和 right 分别指向 0 和 i，其中 left 的作用的是每次找到剩余元素中最小的那一个，它一定是属于 lower 的；right 的作用是指向恰好等于 arr}[\textit{left}] + 2k 的元素，并且将 left 和 right 对应起来；

  • 我们还需要一个长度为 2n 的数组，记录每一个元素是否被使用过。如果指针到达了已经被使用过的元素，则无需处理当前元素；

  • 由于我们还剩余 2n-2 个元素，因此需要进行 n-1 次对应操作。每一次操作中，我们首先向右移动 left 指针，直到指针指向的元素没有被使用过，此时 arr}[\textit{left}] 就是最小的未被使用过的元素，它一定属于 lower。随后我们向右移动 right 指针，直到 arr}[\textit{left}] + 2k = \textit{arr}[\textit{right}] 成立并且 arr 未被使用过。如果不存在这样的元素，那么我们就可以断定剩余的元素无法满足要求；否则，我们就将 arr}[\textit{left}] 和 arr}[\textit{right}] 标记为「使用过」，并将 arr}[\textit{left}] + k（或 arr}[\textit{right}] - k）加入答案。

由于题目保证了「生成的测试用例保证存在至少一个有效数组」，因此上述双指针的方法也一定能找到一个正确的答案。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<int> recoverArray(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 1; i < n; ++i) {
            if (nums[i] == nums[0] || (nums[i] - nums[0]) % 2 != 0) {
                continue;
            }
            
            vector<int> used(n);
            used[0] = used[i] = true;
            int k = (nums[i] - nums[0]) / 2;
            vector<int> ans;
            ans.push_back(nums[0] + k);
            
            int left = 0, right = i;
            for (int j = 2; j + j <= n; ++j) {
                while (used[left]) {
                    ++left;
                }
                while (right < n && (used[right] || nums[right] - nums[left] != k * 2)) {
                    ++right;
                }
                if (right == n) {
                    break;
                }
                ans.push_back(nums[left] + k);
                used[left] = used[right] = true;
            }
            
            if (ans.size() == n / 2) {
                return ans;
            }
        }
        
        // 题目保证一定有解，不会到这一步
        return {};
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def recoverArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        nums.sort()
        for i in range(1, n):
            if nums[i] == nums[0] or (nums[i] - nums[0]) % 2 != 0:
                continue
            
            used = [False] * n
            used[0] = used[i] = True
            k = (nums[i] - nums[0]) // 2
            ans = [nums[0] + k]
            
            left, right = 0, i
            for j in range(1, n // 2):
                while used[left]:
                    left += 1
                while right < n and (used[right] or nums[right] - nums[left] != k * 2):
                    right += 1
                if right == n:
                    break
                ans.append(nums[left] + k)
                used[left] = used[right] = True
            
            if len(ans) == n // 2:
                return ans
        
        # 题目保证一定有解，不会到这一步
        return None

复杂度分析

  • 时间复杂度：O(n^2)。排序需要的时间为 O(n \log n)。枚举 arr}[i] 需要的时间为 O(n)，双指针判断需要的时间为 O(n)，这一部分的总时间为 O(n^2)。

  • 空间复杂度：O(n)。排序需要 O(\log n) 的栈空间。在每一次枚举 arr}[i] 的过程中，我们需要 O(n) 的空间记录每个元素是否被使用过，但枚举之间是互相独立的，因此一共也只需要 O(n) 的空间。

 Comments
On this page
2122-还原原数组