[C++] Clean Code


  • 0
    class Solution {
    public:
        int maximumSwap(int num) {
            string s = to_string(num);
            swaponce(s);
            int l = stoi(s);
            return l;
        }
    private:
        void swaponce(string& s) {
            for (int i = 0; i < s.size(); i++) {
                int maxpos = i;
                for (int j = s.size() - 1; j > i; j--) {
                    if (s[j] > s[maxpos]) {
                        maxpos = j;
                    }
                }
                if (maxpos != i) {
                    swap(s[i], s[maxpos]);
                    break;
                }
            }
        }
    };
    

  • 0
    B

    @alexander You use stol() but store its answer in an int. Why? Also, the question says that The given number is in the range [0, 10^8]; so why is the input (and output) of type int?


  • 0

    @BatCoder I was concerned about the overflow for flipping INT_MAX, then I read the line of 0-108, and I forgot to change it back to stoi :)
    As of int as input type, well, there is no type range exactly from 0-108 right?


  • 0
    G
    This post is deleted!

  • 0
    K

    Your algorithm has a worst case time complexity of O(n^2), when no swap is done.
    I have a similar approach with O(n) worst case time complexity, as in the following:

    int maximumSwap(int num) {        
        string s = to_string(num);
        vector<int> maxId(s.size());
        
        int maxv = -1;
        for (int i = s.size() - 1; i >= 0; i--){
            if (s[i] > maxv) {
                maxv = s[i];
                maxId[i] = i;
            } else {
                maxId[i] =maxId[i+1];
            }   
        }
      
        for (int i=0; i<s.size(); i++){
            if (s[maxId[i]] > s[i]){
                swap(s[i],s[maxId[i]]);
                return stol(s);
            }
        }
        return num;       
    }

Log in to reply
 

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