O(nlogn) solution run faster than O(n) solution?


  • 0
    I

    I wrote two solutions and both of them were accepted.

    1.O(nlogn) base on SORTING, and it took 28ms in average

    class Solution {
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            if (nums.size() < 2) {
                return false;
            }
            vector<pair<int, int> > pairs;
            for (int i = 0; i < nums.size(); i++) {
                pairs.push_back(pair<int, int>(nums[i], i));
            }
            stable_sort(pairs.begin(), pairs.end(), cmp);
            for (int i = 0; i < pairs.size() - 1; i++) {
                if (pairs[i].first == pairs[i+1].first && (pairs[i+1].second - pairs[i].second) <= k) {
                    return true;
                }
            }
            return false;
        }
        static bool cmp(pair<int, int> a, pair<int, int> b) {
            return a.first < b.first;
        }
    };
    

    2.O(n) solution base on hash(unordered_map), and it took 32m in average

    class Solution {
    public:

        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            unordered_map<int, int> hash;
            for (int i = 0; i < nums.size(); i++) {
                if (hash.find(nums[i]) == hash.end()) {
                    hash[nums[i]] = i;
                }
                else {
                    if (i - hash[nums[i]] <= k) {
                        return true;
                    }
                    hash[nums[i]] = i;
                }
            }
            return false;
        }
    };
    

    3.I am confused. WHY???

    PS: there are some reasons that may explain the result I can think of
    3.1 there are some problems in my code.
    3.2 the test cases have bias
    3.3 different run time status of the OJ server.
    3.4 the leetcode cost is not believable(just a random number?)

    4.FXXK the EDITOR


Log in to reply
 

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