Is this a bug?


  • 0
    G

    I wrote my own hash table in C++. When I submitted, it failed to pass the case:
    Input:
    [4,1,-1,2,-1,2,3]
    2
    Output:
    [3,-1]
    Expected:
    [-1,2]
    But when I paste the input to Custom Testcase, my answer met expection:
    Your input:
    [4,1,-1,2,-1,2,3]
    2
    Your anwer:
    [-1,2]
    Expected answer:
    [-1,2]
    I didn't upload screenshot but here's my code:

    template <class T>
    class HashTable
    {
    public:
        HashTable(unsigned int _N)
        : N(_N)
        {
        }
        unsigned int size()
        {
            return m_content.size();
        }
        unsigned int Counti(unsigned int index)
        {
            return m_count[index];
        }
        T &Value(unsigned int index)
        {
            return m_content[index];
        }
        unsigned int Count(T &e)
        {
            auto n = HashFunction(e);
            if (m_head.size() <= n)
            {
                return 0;
            }
            if (!m_exist[n])
            {
                return 0;
            }
            auto p = m_head[n];
            while (m_next[p] != p)
            {
                if (m_content[p] == e)
                {
                    return m_count[p];
                }
                p = m_next[p];
            }
            if (m_content[p] == e)
            {
                return m_count[p];
            }
            return 0;
        }
        unsigned int Insert(T &e)
        {
            auto n = HashFunction(e);
            if (m_head.size() <= n)
            {
                m_head.resize(n + 1, 0);
                m_exist.resize(n + 1, false);
            }
            if (!m_exist[n])
            {
                m_exist[n] = true;
                m_head[n] = m_content.size();
                m_next.push_back(m_content.size());
                m_content.push_back(e);
                m_count.push_back(1);
                return 0;
            }
            auto p = m_head[n];
            while (m_next[p] != p)
            {
                if (m_content[p] == e)
                {
                    m_count[p]++;
                    return m_count[p];
                }
                p = m_next[p];
            }
            if (m_content[p] == e)
            {
                m_count[p]++;
                return m_count[p];
            }
            m_next[p] = m_content.size();
            m_next.push_back(m_content.size());
            m_content.push_back(e);
            return 0;
        }
    private:
        unsigned int N;
        vector<unsigned int> m_count;
        vector<T> m_content;
        vector<unsigned int> m_next;
        vector<unsigned int> m_head;
        vector<bool> m_exist;
        virtual unsigned int HashFunction(int a)
        {
            return a % N;
        }
    };
    
    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            m_pLen = nums.size();
            HashTable<int> hash(m_pLen);
            for (auto &i : nums)
            {
                hash.Insert(i);
            }
            vector<pair<unsigned int, unsigned int>> count;
            for (unsigned int i = 0; i < hash.size(); i++)
            {
                count.push_back({hash.Counti(i), i});
            }
            sort(count.begin(), count.end(), [](pair<unsigned int, unsigned int> &a, pair<unsigned int, unsigned int> &b) -> bool {return a.first > b.first;});
            vector<int> ret;
            for (int i = 0; i < k; i++)
            {
                ret.push_back(hash.Value(count[i].second));
            }
            return ret;
        }
    private:
        unsigned int m_pLen;
    };
    

    Anyone knows what the problem is?


  • 0
    G

    Solved.
    Just add m_count.push_back(1); before the end of function Insert(T &e).

    But still curious why run code was correct...


Log in to reply
 

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