Leetcode medium- single number II

I was solving this question and had the concept charted out well on paper. The problem was though, with the iteration.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> hash;
        for (int i=0; i<nums.size(); i  ){
            hash[nums[i]]  ;
        }
        int x;
        for (auto i:hash){
            if (i.second==1){
                x=i.first;
            }
        }
        return x;
    }
};

The above code solved the question perfectly. But, my initial code got a TLE error (Time Limit Exceeded)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> hash;
        for (int i=0; i<nums.size(); i  ){
            hash[nums[i]]  ;
        }
        int x;
        for (int i=0; i<hash.size(); i  ){
            if (hash[i]==1){
                x= i;
            }
        }
        return x;
    }
};

Here, I have iterated an unordered map in two different ways, both of which ran perfect for the base case. But otherwise, the first code passes while the second goes haywire. This brings me to my two questions-

1. What is wrong with the code? Is it not optimised, or am I doing something incorrect with syntax?
2. Is there a "correct" way to iterate unordered maps? and maybe I did it the second time?

CodePudding user response：

The key saved to the hash need not be in the range from 0 to hash.size().

When hash[i] is calculated with non-existent key i, this results in adding another entry to hash and increase hash.size().

Therefore, depending on the maximum value of the keys, the second loop will run too many times.

Here is a simple example:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> hash;
    hash[1] = 1;
    hash[10] = 10;
    for (int i = 0; i < hash.size(); i  ) {
        std::cout << "i = " << i << ", hash.size() = " << hash.size() << '\n';
        if (hash[i] == 1) {
            std::cout << "hash[i] == 1\n";
        }
    }
    return 0;
}

Result:

i = 0, hash.size() = 2
i = 1, hash.size() = 3
hash[i] == 1
i = 2, hash.size() = 3
i = 3, hash.size() = 4
i = 4, hash.size() = 5
i = 5, hash.size() = 6
i = 6, hash.size() = 7
i = 7, hash.size() = 8
i = 8, hash.size() = 9
i = 9, hash.size() = 10
i = 10, hash.size() = 11

You can see hash.size() is growing after trying non-existent keys.

CodePudding user response：

In general iterators are always going to be faster than operator[], stepping though any container will be faster (or at least not slower for std::vector) than accessing it at random.

unordered_map's operator[] has to calculate the hash of it's parameter then check the items matching that hash for equality. As pointed out by @Someprogrammerdude you also have the problem that if the Key doesn't exist then operator[] will insert a new element into the map, this will result in the map containing every key between 0 and the largest key (which kind of defeats the object of using unordered_map in the first place).

The iterator simply steps through every item in the container without having to do any hash calculations or equality comparisons.

CodePudding user response：

Hint for better solution

There is a better way to do it without std::unordered_map or any container. You should exploit fact that result is shown only once and any other umber appears always three times.

It is possible to create accumulator which will cancel out any value which appears 3 times and leave only single item which appeared exactly once.

I was able to pass this on leetcode with time 7ms (I reached limit of time resolution on leetcode). In my code there are only 4 int variables and couple crafty bit-wise operations on them.

For know I will not post solution to not spoil fun to finding this solution.

About iterating over std::unorered_map

There is no room to do significant improvement in your code to use of this container. You can add just early termination of a loop and reference:

        for (const auto& i:hash){
            if (i.second==1){
                return i.first;
            }
        }
        return 0;

With your current approach, literally you can't do anything to make it significantly faster.

In your second approach you are not iterating over items of hash you are in fact adding new entries if the do not exists with key i and zero value.