原地调整法查找数组元素

原地调整法查找数组元素

题目描述

这一类题目一般是给出一个数组,数组元素的取值范围在 1~n 之间,其中 n 是数组元素个数,然后要求找出缺失元素或者重复元素,缺失或重复的元素可以是一个或多个。例如:

之前在字节跳动的面试中就曾经出现过一道类似题目。

解题思路

对于这种题目,最简单的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
上一篇:哈希表设计


下一篇:动态树Link-Cut-Tree