Simple AC O(n) java solution with ex


  • 6
    L

    Very similar to LeetCode 31. Next Permutation

    1. Search from the left end and find the position where the reversed list was not satisfied. (example. in number 54367, we will find the position of 6.) Then we cut the original digits array to two parts, the first part was reversely sorted which means no swap needed within it and the second part.
    2. Find and record the max value and max value position in the second part. ( example, digit 7 in 54367)
    3. Swap the max value in the second part to the first number in first part that smaller than that max value. (Example, swap 7 with 5 in 54367)
      Time Complexity is O(n)
    public int maximumSwap(int num) {
        char[] digits = (""+num).toCharArray();
        int frist_greater = 0; //find the first digit greater than previous
        while(++frist_greater<digits.length&&digits[frist_greater-1]>=digits[frist_greater]);
        if(frist_greater==digits.length) return num; //all digits are reversed sorted, no swap needed
        
        char max = '0';               
        int max_position=frist_greater;    
        for(int i=frist_greater;i<digits.length;i++)//find max digit in remain digits
            if(max<=digits[i]){
                max = digits[i];
                max_position = i;
            }
        
        for(int i=0;i<frist_greater;i++)  //find first digit that smaller than max digit in the second part
            if(max>digits[i]){
                StringBuilder s = new StringBuilder(String.valueOf(digits));
                s.setCharAt(max_position,digits[i]);
                s.setCharAt(i,max);
                return Integer.parseInt(s.toString());  //no need to check overflow since max value is 10^8
            }
        return num;
    }

  • 2
    Z

    牛逼啊
    6666666666666


  • 0
    Y

    贼牛逼,楼主写的就是好
    三五瓶
    逼两拳
    还来一套军体拳


  • 0
    R

    楼主威武,顶!!!!为这种好答案给个赞


  • 0
    C

    I agreeedg;lkhbporthbjrtj ioien m mlmvlvkeu456859idjkbtASDOLP;'#
    ]=P-8TREDS3456U7I89GIYJPOTVBES


Log in to reply
 

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