class Solution {
public:
vector<int> recoverArray(vector<int>& nums) {
}
};
2122. 还原原数组
Alice 有一个下标从 0 开始的数组 arr ，由 n 个正整数组成。她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher ：
0 <= i < n 的下标 i ，lower[i] = arr[i] - k0 <= 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.length1 <= n <= 10001 <= nums[i] <= 109arr原站题解
cpp 解法, 执行用时: 32 ms, 内存消耗: 19.3 MB, 提交时间: 2023-09-14 01:00:37
class Solution {
public:
vector<int> recoverArray(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 1; i < n; i++) {
int d = nums[i] - nums[0];
if ( d == 0 || d & 1 > 0) continue;
int k = d/2;
vector<bool> vis(n);
vis[i] = true;
vector<int> res {nums[i] + nums[0] >> 1};
int l = 1, r = i + 1;
while (r < n) {
while(l < n && vis[l]) l++;
while(r < n && nums[r] - nums[l] < 2 * k) r++;
if (r == n || nums[r] - nums[l] > 2 * k) break;
vis[r] = true;
res.push_back(nums[l] + nums[r] >> 1);
r++;
l++;
}
if (res.size() == n/2) return res;
}
return {};
}
};
java 解法, 执行用时: 6 ms, 内存消耗: 42.7 MB, 提交时间: 2023-09-14 01:00:20
class Solution {
public int[] recoverArray(int[] nums) {
Arrays.sort(nums);
int m = nums.length;
int[] ans = new int[m / 2];
for (int i = 1; i < m; i++) {
//nums[0] 必定是第一个值，用nums中的其他值枚举
int diff = nums[i] - nums[0];
// diff不为奇数和0
if (diff % 2 == 1 || diff == 0) continue;
int k = diff / 2;
ans[0] = nums[0] + nums[i] >> 1;
//数组下标
int idx = 1;
//l从1开始
int l = 1;
//r从i+1开始 如果nums[i]为目标值的higher，那个下一个值+k 一定比nums[i]大
int r = i + 1;
boolean[] visited = new boolean[m];
visited[i] = true;
while (r < m) {
//i+1后是没有被遍历过的，r遍历过的不能遍历，l遍历过的在l和r前面
while (l < m && visited[l]) l++;
//需要大于2*k才可能
//r不可能等于l
while (r < m && nums[r] - nums[l] < 2 * k) r++;
//边界 或者 大于2*k 则无效
if (r == m || nums[r] - nums[l] > 2 * k) break;
visited[r] = true;
ans[idx] = nums[r] + nums[l] >> 1;
idx++;
l++;
r++;
}
//第一次满足，直接返回，lower[0]对应的higher[0]肯定是在比较前面的
if (idx == m / 2) return ans;
}
return ans;
}
}
python3 解法, 执行用时: 180 ms, 内存消耗: 16.3 MB, 提交时间: 2023-09-14 01:00:03
class Solution:
def recoverArray(self, nums: List[int]) -> List[int]:
nums.sort()
n=len(nums)
for i in range(1,n//2+1):
d = nums[i]-nums[0]
if d==0 or d%2==1:continue
visited=[False]*n
visited[i]=True
res = [(nums[i]+nums[0])>>1]
lo,hi=1,i+1
while hi<n:
while lo<n and visited[lo]:
lo+=1
while hi<n and nums[hi]-nums[lo]<d:
hi+=1
if hi==n or nums[hi]-nums[lo]>d:
break
visited[hi]=True
res.append((nums[lo]+nums[hi])>>1)
lo+=1
hi+=1
if len(res)==n//2:return res
return []
golang 解法, 执行用时: 16 ms, 内存消耗: 6.9 MB, 提交时间: 2023-09-14 00:59:39
func recoverArray(nums []int) []int {
sort.Ints(nums)
for i, n := 1, len(nums); ; i++ {
if nums[i] == nums[i-1] { continue } // 优化：如果与上一个元素相同，那么我们会得到同样的 k，同样找不到原数组，此时应直接跳过
d := nums[i] - nums[0] // 此时 d > 0 必然成立
if d&1 > 0 { continue } // k 必须是整数
k := d / 2
vis := make([]bool, n) // 用来标记出现在 higher 中的数（用 nums 的下标）
vis[i] = true
ans := []int{(nums[0] + nums[i]) / 2}
for lo, hi := 0, i+1; hi < n; hi++ { // 双指针：lo 指向 lower，hi 指向 higher
for lo++; vis[lo]; lo++ {} // 找 lower：跳过出现在 higher 中的数
for ; hi < n && nums[hi]-nums[lo] < 2*k; hi++ {} // 找 higher
if hi == n || nums[hi]-nums[lo] > 2*k { break } // 不存在满足等式的 higher 值
vis[hi] = true
ans = append(ans, (nums[lo]+nums[hi])/2) // 找到一对满足等式的 (lower, higher)
}
if len(ans) == n/2 { return ans }
}
}