Hard
题目描述
Alice 有一个由 n 个正整数组成的下标从 0 开始的数组 arr。她选择一个任意的正整数 k，并按照下述方式创建两个新的下标从 0 开始的整数数组 lower 和 higher：
- lower[i] = arr[i] - k，对于每个满足 0 <= i < n 的下标 i
- higher[i] = arr[i] + k，对于每个满足 0 <= i < n 的下标 i
不幸的是，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。
注意 arr 不能是 [1,3]，因为在这种情况下，获得 [1,1,3,3] 的唯一可能方式是 k = 0。
这无效，因为 k 必须是正数。
提示：
- 2 * n == nums.length
- 1 <= n <= 1000
- 1 <= nums[i] <= 10^9
- 生成的测试用例保证至少存在一个有效的数组 arr
解题思路
解题思路
这道题的关键在于如何确定参数 k 的值。我们需要理解题目的本质：给定数组 nums 包含了原数组中每个元素减去 k 和加上 k 的结果。
核心观察：
- 原数组的最小值减去 k 后，一定是 nums 中的最小值
- 对于任意可能的 k 值，我们可以尝试重构原数组并验证其有效性
算法步骤：
排序数组：首先对 nums 进行排序，这样可以方便地处理配对问题
枚举可能的 k 值：
- nums[0] 一定来自某个原数组元素减去 k
- 对于每个 nums[i]（i > 0），如果它来自同一个原数组元素加上 k，那么 k = (nums[i] - nums[0]) / 2
- 由于 k 必须是正整数，所以 nums[i] - nums[0] 必须是正偶数
验证 k 值的有效性：
- 使用贪心策略：对于排序后的数组，尝试将每个未配对的最小元素作为 lower 值
- 在剩余元素中寻找对应的 higher 值（即当前值 + 2k）
- 如果能成功配对所有元素，说明这个 k 值有效
重构原数组：一旦找到有效的 k，原数组中的每个元素就是对应的 lower 值加上 k
时间复杂度分析：
- 外层循环最多 n 次（枚举可能的 k）
- 内层验证过程需要 O(n log n)（主要是查找操作）
- 总体时间复杂度为 O(n² log n)
代码实现
class Solution {
public:
vector<int> recoverArray(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size() / 2;
for (int i = 1; i < nums.size(); i++) {
if ((nums[i] - nums[0]) % 2 != 0) continue;
int k = (nums[i] - nums[0]) / 2;
if (k == 0) continue;
multiset<int> remaining(nums.begin(), nums.end());
vector<int> result;
bool valid = true;
while (!remaining.empty() && valid) {
int lower = *remaining.begin();
remaining.erase(remaining.begin());
int higher = lower + 2 * k;
auto it = remaining.find(higher);
if (it != remaining.end()) {
remaining.erase(it);
result.push_back(lower + k);
} else {
valid = false;
}
}
if (valid && result.size() == n) {
return result;
}
}
return {};
}
};
class Solution:
def recoverArray(self, nums: List[int]) -> List[int]:
nums.sort()
n = len(nums) // 2
for i in range(1, len(nums)):
if (nums[i] - nums[0]) % 2 != 0:
continue
k = (nums[i] - nums[0]) // 2
if k == 0:
continue
remaining = Counter(nums)
result = []
valid = True
for num in sorted(remaining.keys()):
while remaining[num] > 0 and valid:
lower = num
higher = lower + 2 * k
if remaining[higher] > 0:
remaining[lower] -= 1
remaining[higher] -= 1
result.append(lower + k)
else:
valid = False
break
if valid and len(result) == n:
return result
return []
public class Solution {
public int[] RecoverArray(int[] nums) {
Array.Sort(nums);
int n = nums.Length / 2;
for (int i = 1; i < nums.Length; i++) {
if ((nums[i] - nums[0]) % 2 != 0) continue;
int k = (nums[i] - nums[0]) / 2;
if (k == 0) continue;
var remaining = new Dictionary<int, int>();
foreach (int num in nums) {
remaining[num] = remaining.GetValueOrDefault(num, 0) + 1;
}
var result = new List<int>();
bool valid = true;
foreach (int num in nums.OrderBy(x => x)) {
while (remaining.GetValueOrDefault(num, 0) > 0 && valid) {
int lower = num;
int higher = lower + 2 * k;
if (remaining.GetValueOrDefault(higher, 0) > 0) {
remaining[lower]--;
remaining[higher]--;
result.Add(lower + k);
} else {
valid = false;
break;
}
}
if (!valid) break;
}
if (valid && result.Count == n) {
return result.ToArray();
}
}
return new int[0];
}
}
/**
* @param {number[]} nums
* @return {number[]}
*/
var recoverArray = function(nums) {
nums.sort((a, b) => a - b);
const n = nums.length / 2;
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[0]) continue;
const diff = nums[i] - nums[0];
if (diff % 2 !== 0) continue;
const k = diff / 2;
const used = new Array(nums.length).fill(false);
const result = [];
let j = 0;
while (j < nums.length && result.length < n) {
if (used[j]) {
j++;
continue;
}
const lower = nums[j];
const higher = lower + 2 * k;
let higherIndex = -1;
for (let l = j + 1; l < nums.length; l++) {
if (!used[l] && nums[l] === higher) {
higherIndex = l;
break;
}
}
if (higherIndex === -1) break;
used[j] = true;
used[higherIndex] = true;
result.push(lower + k);
j++;
}
if (result.length === n) {
return result;
}
}
return [];
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n² log n) | 外层循环 O(n)，内层验证 O(n log n) |
| 空间复杂度 | O(n) | 存储计数器和结果数组 |