C++ Solution without swap, my accept solution


  • 1
    D

    Inspired by the problem Find All Numbers Disappeared in an Array, I've got this solution below:

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

    Given that each element is between 1 and n. All the elements occur either once or twice.
    I use one pass, every time an element occurs, mark its corresponding index negate. So if one element occurs twice, when it come to its second appearance, it will found the corresponding index was negate. So, this element is what we're interested in.

    For example, array A = [4, 3, 2, 4, 1], when first met 4, A[3] come to -4, but when met 4 secondly, we found A[3] is already negate, so we would know that, 4 show twice.

    I thought this works as well~


Log in to reply
 

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