原地调整法查找数组元素
题目描述
这一类题目一般是给出一个数组,数组元素的取值范围在 1~n 之间,其中 n 是数组元素个数,然后要求找出缺失元素或者重复元素,缺失或重复的元素可以是一个或多个。例如:
- LeetCode 448. Find All Numbers Disappeared in an Array
- LeetCode 287. Find the Duplicate Number
- LeetCode 442. Find All Duplicates in an Array
之前在字节跳动的面试中就曾经出现过一道类似题目。
解题思路
对于这种题目,最简单的O(N)空间做法其实是开一个vis数组(bool数组或者bitmap均可),然后尝试用每一个元素去标记是否访问过,这样的时间复杂度也是O(N)。
但是我们其实可以在O(1)空间内解决问题,思路其实就是三个字 调整法。
既然数组元素值与下标存在对应关系,那么我们就去做调整,把每个元素调整到自己对应的下标上去,如果出现了碰撞,说明是重复;如果出现了空穴,说明是缺失。
参考代码
LeetCode 448. 查找缺失元素,有一个
/*
* @lc app=leetcode id=448 lang=cpp
*
* [448] Find All Numbers Disappeared in an Array
*/
// @lc code=start
class Solution {
public:
// 有的元素出现2次,有的出现1次,有的没出现过;找出没出现过的
vector<int> findDisappearedNumbers(vector<int>& nums) {
for(int i=0; i<nums.size(); i++) {
int& v = nums[i]; // 一定得是引用,不能是值。while要用多次
while(nums[i] != i+1 && nums[v-1] != v) {
swap(nums[i], nums[v-1]);
} // 把元素调整到自己对应位置上去
}
vector<int> res;
for(int i=0; i<nums.size(); i++) {
if(nums[i] != i+1) {
res.push_back(i+1);
} // 调整不过去,说明这个地方元素缺失了
}
return res;
}
};
// @lc code=end
LeetCode 287. 查找重复元素,有一个
/*
* @lc app=leetcode id=287 lang=cpp
*
* [287] Find the Duplicate Number
*/
// @lc code=start
class Solution {
public:
int findDuplicate(vector<int>& nums) {
for(int i=0; i<nums.size(); i++) {
while(nums[i] != i+1) {
int x = nums[i];
if (x == nums[x-1]) return x;
nums[i] = nums[x-1];
nums[x-1] = x;
}
}
return -1;
}
};
// @lc code=end
LeetCode 442. 查找重复元素,有多个
/*
* @lc app=leetcode id=442 lang=cpp
*
* [442] Find All Duplicates in an Array
*/
// @lc code=start
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
int n = nums.size();
for (int i=0; i<n; i++) {
while (nums[i] != i+1) {
if (nums[i] < 0) break; // invalid
int j = nums[i] - 1;
if (nums[i] == nums[j]) { // == j+1
res.push_back(nums[j]);
nums[j] = -1;
break;
}
swap(nums[i], nums[j]);
}
}
return res;
} // AC
};
// @lc code=end