C++ with no sets or anything


  • 0
    M

    The little 'topthree' struct just stores the top 1, 2, or 3 values inserted. Values are inserted/evicted by a search through the existing elements.

    This clocks in at 9 ms -- still slower than some of the C 'insertion-sort' solutions.

        class Solution {
        public:
            int thirdMax(vector<int>& nums)
            {
                // Store the top three inserted elements
                struct topthree
                {
                    int* begin() { return vals + 0; }
                    int* end() { return vals + cnt; }
    
                    bool contains(int val)
                    { return find(begin(), end(), val) != end(); }
    
                    int max() 
                    {
                        if (cnt == 3)
                            return *min_element(begin(), end());
                            
                        return *max_element(begin(), end());
                    }
    
                    void insert(int val) 
                    {
                        if (cnt == 3)
                        {
                            // Evict the smallest by placing it as the last element.
                            vals[3] = val;
                            swap(*min_element(begin(), end() + 1), vals[3]);
                        }
                        else {
                            vals[cnt++] = val;
                        }
                    }
    
                    int cnt = 0;
                    int vals[4] = {};
                };
                
                topthree vals;
                for (auto num : nums)
                {
                    if (!vals.contains(num))
                        vals.insert(num);
                }
    
                return vals.max();
            }
        };
    

Log in to reply
 

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