排序+双指针题目类型
排序+双指针题目类型
1.从双倍数组中还原原数组
题目：
一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。
给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。
示例 1：
输入：changed = [1,3,4,2,6,8] 输出：[1,3,4] 解释：一个可能的 original 数组为 [1,3,4] :
- 将 1 乘以 2 ，得到 1 * 2 = 2 。
- 将 3 乘以 2 ，得到 3 * 2 = 6 。
- 将 4 乘以 2 ，得到 4 * 2 = 8 。其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。
题解：
先排序，随后利用双指针往前遍历，由于left指针要跳到下一个left，中间会有right指针，因此需要使用一个set记录已经访问过的。
实现：
class Solution {
public:
vector<int> findOriginalArray(vector<int>& changed) {
sort(changed.begin(), changed.end());
int l = 0, r = 1;
int n = changed.size();
if (n % 2) return {};
vector<int> ans;
set<int> s;
while (r < n) {
while (l < n && s.count(l)) { l++; }
// 排除0
if (changed[r] == changed[l]) {
r = l + 1;
}
while (r < n && changed[r] < 2*changed[l]) { r++; }
if (r == n || changed[r] > 2 * changed[l]) {
break;
}
s.insert(l);
s.insert(r);
ans.push_back(changed[l]);
l++;
r++;
}
if (ans.size() != n / 2) return {};
return ans;
}
};
2.还原原数组
题目：
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倍来判断，这道题则是根据+k与-k判断，对于+k与-k则是后面一个数-前面一个数 除以 2 的到这个k，那么对于第一个数来说，一定是lower当中的，我们遍历除了第一个元素之后的每个元素作为higher的第一个元素，从而拿到k，随后根据这个k去按照上面题目双指针找到所有满足条件的数据，最后判断是否恰好找到即可。
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++) {
if (nums[i] == nums[i - 1]) {
continue;
}
vector<int> ans;
int k = (nums[i] - nums[0]) / 2;
if ((nums[i] - nums[0]) % 2) {
continue;
}
set<int> s{0,i};
int l = 0, r = i + 1;
ans.push_back(nums[i] - k);
// 2 4 6 8 10 12
while (r < n) {
while (l < n && s.count(l)) { l++; }
while (r < n && (nums[r] - nums[l]) < 2 * k) { r++; }
if (r == n || (nums[r] - nums[l]) > 2 * k) {
break;
}
s.insert(l);
s.insert(r);
ans.push_back((nums[r] + nums[l]) / 2);
l++;
r++;
}
if (ans.size() == n / 2) {
return ans;
}
}
return vector<int>();
}
};