2022-04-27：Alice 有一个下标从 0 开始的数组 arr ，由 n 个正整数组成。她会选择一个任意的 正整数 k
2022-04-27：Alice 有一个下标从 0 开始的数组 arr ，由 n 个正整数组成。她会选择一个任意的 正整数 k
2022-04-27：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 。
输入：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] 。
力扣2122. 还原原数组。
来自小米。
答案2022-04-27：
先排序。大数的第1个数需要循环。
时间复杂度：O(N**2)。
代码用rust编写。代码如下：
fn main() {
let mut nums: Vec<isize> = vec![2, 10, 6, 4, 8, 12];
let ans: Vec<isize> = recover_array(&mut nums);
println!("ans = {:?}", ans);
}
fn recover_array(nums: &mut Vec<isize>) -> Vec<isize> {
nums.sort_by(|a, b| a.cmp(&b));
let n = nums.len() as isize;
// nums[0] -> 小数组的第0个
let m = n >> 1;
// 谁是大数组的第0个？不知道，试！first位置的数！
for first in 1..=m {
// d = 2 * k; k正数！
let d = nums[first as usize] - nums[0];
if d > 0 && (d & 1) == 0 {
// 试图生成原始数组！ans！
let mut ans: Vec<isize> = vec![];
for _k in 0..m {
ans.push(0);
}
let mut i: isize = 0;
let mut set: Vec<bool> = vec![];
for _k in 0..n {
set.push(false);
}
let k: isize = d >> 1;
let mut l: isize = 0;
let mut r: isize = first;
while r < n {
while set[l as usize] {
l += 1;
}
if l == r {
r += 1;
} else if nums[r as usize] - nums[l as usize] > d {
break;
} else if nums[r as usize] - nums[l as usize] < d {
r += 1;
} else {
set[r as usize] = true;
r += 1;
ans[i as usize] = nums[l as usize] + k;
l += 1;
i += 1;
}
}
if i == m {
return ans;
}
}
}
return vec![];
}执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_02_2_week/Code05_RecoverTheOriginalArray.java)