C++ Solution O(1) space complexity O(n) time complexity


  • 0
    N

    The idea is to use (nums[i]-1) as an index because all number are in range 1~n, we set nums[nums[i]-1] to be negative.
    In first for loop, we set all to negative. If we find a number that is already negative, nums[i] is the number which appears twice.
    In second for loop, we iterate the whole array and find the only one is positive, then (i+1) is the number missing because no index pointed to this value so it is still positive.
    Also, since(nums[i]) might be negative, we use abs(nums[i]) to indicate all the index.

    class Solution {
    public:
        vector<int> findErrorNums(vector<int>& nums) {
            vector<int> res;
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[abs(nums[i])-1] < 0) { res.push_back(abs(nums[i])); }
                else { nums[abs(nums[i])-1] = -nums[abs(nums[i])-1]; }
            }
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] > 0)  res.push_back(i+1);
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.