online advertising

Saturday, August 5, 2017

LeetCode OJ - Set Mismatch

Problem:

Please find the problem here.

Solution:

My idea is sorting - if we sort the array, then we basically get the answer. A naive sorting would take $ O(n \log n) $ time, but a simple one could be done by pushing numbers.

In particular, imagine the numbers are put in the array like stone put in boxes. Let's start from a box where it has a wrong number to begin with, take the number away the slot, we have an empty box there and a stone outside.

But we know where that stone should go, there could be a few cases:

Case 1: The box has the right number already

This is easy, we have found our duplicate!

Case 2: The box is empty.

Just put the right number in, and try another slot with a wrong number.

Case 3: The box has a wrong number.

In this case, we pick the wrong number up and put the right number in, and do the whole thing again.

Eventually, we will find the duplicate. Once we have the duplicate known, we can easily find the missed number by comparing the sums.

Consider the difference of expected sum - actual sum, every number in the sums should cancel out except the missing number - the duplicated number, so if we know the duplicated number, the missing number can be calculated by the sums.

Analysis:

The algorithm is fine, but is it fast? We claim the algorithm is linear. Computing sum is linear, trying the slot is linear, the only unclear part is how many iterations the while loop could run, while a single instance of the while loop could be bad, we claim that the total number of iterations for all while loop iteration must be $ O(n) $, this is because for each iteration that does not end the while loop, the iteration must bring one slot from its incorrect state to its correct state, that can happen only once per slot. Therefore we claim this is a linear time algorithm.

Moreover, this obviously does not take up extra space, this should be optimal. We could have also solve this problem with a hash table or another array with the same size, but that would mean extra space.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/set-mismatch/description/

#include "LEET_SET_MISMATCH.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_SET_MISMATCH
{
    class Solution
    {
    public:
        vector<int> findErrorNums(vector<int>& nums)
        {
            vector<int> result;
            int n = (int)nums.size();
            int duplicated = -1;
            int sum = 0;
            int correct_sum = (n + 1) * n / 2;
            for (int i = 0; i < n; i++)
            {
                sum += nums[i];
            }
            for (int i = 1; i <= n; i++)
            {
                int value = i;
                int index = value - 1;

                if (nums[index] == value)
                {
                    continue;
                }

                value = nums[index];
                nums[index] = -1;
                index = value - 1;

                while (true)
                {
                    if (nums[index] == value)
                    {
                        duplicated = value;
                        break;
                    }
                    else if (nums[index] == -1)
                    {
                        nums[index] = value;
                        break;
                    }
                    else
                    {
                        int next_value = nums[index];
                        nums[index] = value;
                        value = next_value;
                        index = value - 1;
                    }
                }

                if (duplicated != -1)
                {
                    break;
                }
            }
            result.push_back(duplicated);
            result.push_back(correct_sum - sum + duplicated);
            return result;
        }
    };
};

using namespace _LEET_SET_MISMATCH;

int LEET_SET_MISMATCH()
{
    Solution solution;
    int test_array[] = { 2, 4, 1, 2 };
    vector<int> test(test_array, test_array + _countof(test_array));
    vector<int> result = solution.findErrorNums(test);
    cout << result[0] << " " << result[1] << endl;
    return 0;
}

No comments :

Post a Comment