645. Set Mismatch

Posted on 3 mins read

1. Description

The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.
Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

2. Example

Example 1:
Input: nums = [1,2,2,4]
Output: [2,3]

3. Note

  • The given array size will in the range [2, 10000].
  • The given array’s numbers won’t have any order.

4. Solutions

My Accepted Solution

n = m_nums.size()
Time complexity: O(n)
Space complexity: O(1)

// return all values to its responding position(responded to its index)

class Solution 
{
public:
    // vector<int> findErrorNums(vector<int>& nums)
    vector<int> findErrorNums(vector<int> &m_nums) 
    {
        for(int i = 0; i < m_nums.size(); i++)
        {
            while(m_nums[i] != i + 1)
            {
                if(m_nums[m_nums[i] - 1] == m_nums[i]) break;
                    
                swap(m_nums[i], m_nums[m_nums[i] - 1]);
            }
        }
        
        for(int i = 0; i < m_nums.size(); i++)
        {
            if(m_nums[i] != i + 1)
            {
                return vector<int>{m_nums[i], i + 1};
            }
        }
        
        return vector<int>{};
    }
};

4.1 Revert Values to Negative

n = m_nums.size()
Time complexity: O(n)
Space complexity: O(1)

// this methord looks like my solution, but it turns all iterated values to negative
// then, if a value is positive, it has been iterated twice
// so, it is the duplicate

class Solution 
{
public:
    // vector<int> findErrorNums(vector<int>& nums)
    vector<int> findErrorNums(vector<int> &m_nums) 
    {
        int duplicate, missing;
        for(int i = 0; i < m_nums.size(); i++)
        {
            if(m_nums[abs(m_nums[i]) - 1] < 0)
                duplicate = abs(m_nums[i]);
            else
                m_nums[abs(m_nums[i]) - 1] *= -1;
        }
        
        for(int i = 0; i < m_nums.size(); i++)
        {
            if(m_nums[i] > 0)
            {
                missing = i + 1;
                break;
            }
        }
        
        return vector<int>{duplicate, missing};
    }
};

4.2 XOR

n = m_nums.size()
Time complexity: O(n)
Space complexity: O(1)

// n = m_nums.size()
// Time complexity : O(n)
// Space complexity : O(1)

// this is the Leetcode's official solution
// I think there is no advatanges of this methord 😑, and it is too tedious

public class Solution {
    public int[] findErrorNums(int[] nums) {
        int xor = 0, xor0 = 0, xor1 = 0;
        for (int n: nums)
            xor ^= n;
        for (int i = 1; i <= nums.length; i++)
            xor ^= i;
        int rightmostbit = xor & ~(xor - 1);
        for (int n: nums) {
            if ((n & rightmostbit) != 0)
                xor1 ^= n;
            else
                xor0 ^= n;
        }
        for (int i = 1; i <= nums.length; i++) {
            if ((i & rightmostbit) != 0)
                xor1 ^= i;
            else
                xor0 ^= i;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == xor0)
                return new int[]{xor0, xor1};
        }
        return new int[]{xor1, xor0};
    }
}
comments powered by Disqus