C++ O(n) using multimap---easy to understand


  • 0

    Using multimap to save the digits and locations of num, multimap saves keys by default in order, and then traverse multimap from the end to begin, swap if the digit isn't in the right location.

    class Solution {
    public:
        int maximumSwap(int num) {
            string str=to_string(num);
            multimap<int, int>numLoc;
            for(int i=0;i<str.size();++i)
                numLoc.insert(make_pair(str[i]-'0',i));
            multimap<int, int>::reverse_iterator iter=numLoc.rbegin(), next;
            int i=0;
            while(iter!=numLoc.rend()){
                next=++iter;
                --iter;
                if(iter->second!=i){
                    if(str[iter->second]!=str[i]){
                        swap(str[iter->second], str[i]);
                        break;
                    }
                    else{
                        swap(iter->second, next->second);
                        iter++;
                        i++;
                    }              
                }
                else{
                    iter++;
                    i++;
                }
            }
            return stoi(str);
        }
    };
    

Log in to reply
 

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