leetcode 448. 找到所有数组中消失的数字

leetcode

1. 标记法
   C++：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {

        for ( int i = 0; i < nums.size(); ++i ) {

            int number = abs(nums[i]);
            int index = number - 1;

            if ( nums[index] > 0 ) {

                nums[index] *= -1;
            }
        }

        std::vector<int> results;
        for ( int i = 0; i < nums.size(); ++i ) {

            if ( nums[i] > 0 ) {

                results.push_back(i + 1);
            }
        }

        return results;
    }
};

2. 原地哈希法
   C++

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {

        for ( int i = 0; i < nums.size(); ++i ) {

            while ( nums[i] != nums[nums[i] - 1] ) {

                std::swap(nums[i], nums[nums[i] - 1]);
            }
        }

        std::vector<int> results;
        for ( int i = 0; i < nums.size(); ++i ) {

            if ( nums[i] != i + 1) {

                results.push_back(i + 1);
            }
        }

        return results;
    }
};