Monday, August 10, 2015

LeetCode OJ - Contains Duplicate II

Problem:

Please find the problem here.

Solution:

Instead of using a map, just sort the array with their positions and do a scan, that involves $ O(n) $ space, if space is an issue, I could optimize it to $ O(k) $ space if needed by building a balanced search tree of the running $ k $ elements, in addition, that will produce an algorithm that runs in $ O(n \log k) $ time, which is faster than $ O(n \log n) $.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/contains-duplicate-ii/

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

using namespace std;

namespace _LEET_CONTAINS_DUPLICATE_II
{
    class Solution
    {
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k)
        {
            vector<pair<int, unsigned int>> nums_with_position;
            nums_with_position.resize(nums.size());
            for (unsigned int i = 0; i < nums.size(); i++)
            {
                nums_with_position[i] = pair<int, unsigned >(nums[i], i);
            }
            sort(nums_with_position.begin(), nums_with_position.end());
            for (unsigned int i = 1; i < nums.size(); i++)
            {
                if (nums_with_position[i - 1].first == nums_with_position[i].first)
                {
                    if (nums_with_position[i].second - nums_with_position[i - 1].second <= k)
                    {
                        return true;
                    }
                }
            }
            return false;
        }
    };
};

using namespace _LEET_CONTAINS_DUPLICATE_II;

int LEET_CONTAINS_DUPLICATE_II()
{
    Solution solution;
    int case1[] = { 3, 2, 3 };
    cout << !solution.containsNearbyDuplicate(vector<int>(case1, case1 + _countof(case1)), 1) << endl;
    cout << solution.containsNearbyDuplicate(vector<int>(case1, case1 + _countof(case1)), 2) << endl;
    return 0;
}

No comments :

Post a Comment