c++ slow, but different approach


  • 0
    G

    Test case:
    (7,0) (4,4) (7,1) (5,0) (6,1) (5,2)
    After sorts:
    (4,4) (5,0) (5,2) (6,1) (7,0) (7,1)

    Start at the end of the array. Move elements right by the difference of: (count of people at or greater to current height) and (other people at current height to the left).

    (4,4) (5,0) (5,2) (6,1) (7,0) (6,1) (7,1)
    (4,4) (5,0) (5,2) (7,0) (5,2) (6,1) (7,1)

    Kind of like insertion sort married its cousin and had a dyslexic child. I didn't bother with optimizations, but they are plentiful. The sorts could be combined for starters, which would get rid of the need for stable. Depending on how far elements need to shift, using an intermediary list may be beneficial as well.

    There are definitely better, cleaner solutions in the discussion. Some of you are freaking smart. This way seems more intuitive to me and is easier for me to visualize. YMMV.

    class Solution {
    public:
        vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) 
        {
            int size = people.size();
            vector<pair<int, int>> result;
    
            typedef pair<int, int> IntPair;
            sort(people.begin(), people.end(), [](const IntPair& p1, const IntPair& p2)
            {
                return p1.second < p2.second;
            });
            
            stable_sort(people.begin(), people.end(), [](const IntPair& p1, const IntPair& p2)
            {
                return p1.first < p2.first;
            });
            
            int cur = size - 1;
    
            while(cur >= 0)        
            {
                int maxHeight = people[cur].first;
                int r = cur;
                while(people[r].first == maxHeight)
                {
                    --r;
                }
                int same = cur - (r + 1);
                
                int numMoves = people[cur].second - same;
                for(int i = 0; i < numMoves; ++i)
                {
                    swap(people[cur + i], people[cur + i + 1]);
                }
                --cur;
            }
    
            return people;
        }
    };
    

Log in to reply
 

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