C++ Simply Solution without Swap w/ Detail Explanation


  • 0
    L

    The basic idea is to use the number value (-1) as the index. If the number exists, negate the value. Then, after one loop we can find which value is missing in the array (actually it's solution to question 448). Then we start loop the array again and negate number. If a number appears twice, its indexed number will be negate twice which is still negative.

    Example below:

    2, 3, 2, 4, 3, 1, 5 // first loop changes it to
    -2, -3, -2, -4, -3, 1, 5; // positive number mean val = its index+1 is missing. i.e 6 7 is missing
    // then we loop through the array again and for use the abs(nums[i])-1 as index to negate the number. Finally we get:
    2, -3, -2, 4, 3, 1, 5; // negative number means its index +1 has been appeared twice, i.e 2 and 3.

    class Solution {
    public:
        vector<int> findDuplicates(vector<int>& nums) {
            vector<int> vec;
    
            // step 1: missing numbers index number is still positive
            for (int i=0; i<nums.size(); ++i) {
                int id = abs(nums[i])-1;
                nums[id] = nums[id] > 0 ? -nums[id] : nums[id];
            }
            // step 2: number indexed number is negated. If a number appears twice, its indexed number will be negated twice and it's still negative.
            for (int i=0; i<nums.size(); ++i) {
                int id = abs(nums[i])-1;
                nums[id] = -nums[id];
            }
            // step 3: find all negative number. its index appeared twice.
            for (int i=0; i<nums.size(); ++i) {
                if (nums[i] < 0) vec.push_back(i+1);
            }
            return vec;
        }
    };
    

Log in to reply
 

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