Java solution, brute force


  • 1
    class Solution {
        public int maximumSwap(int num) {
            char[] arr = (num + "").toCharArray();
            for (int i = 0; i < arr.length - 1; i++) {
                int k = -1, idx = -1;
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[j] >= k) {
                        k = arr[j];
                        idx = j;
                    }
                }
                if (arr[i] < k) {
                    arr[idx] = arr[i];
                    arr[i] = (char)k;
                    int res = 0;
                    for (int l = 0; l < arr.length; l++) {
                        res = res * 10 + arr[l] - '0';
                    }
                    return res;
                }
            }
            
            return num;
        }
    }
    

  • 1
    B

    I saved the index for each number and sort the original array.

    public class Solution 
    {
        public int MaximumSwap(int num) 
        {
            var numArray = $"{num}".ToCharArray();
    
            var numAndIndex = new Dictionary<char, int>();
    
            for(int i = 0; i < numArray.Length; i++)
            {
                numAndIndex[numArray[i]] = i;
            }
    
            var sortedNumArray = $"{num}".ToCharArray();
            Array.Sort(sortedNumArray, (a,b)=>b-a);
    
            for (int i = 0; i < numArray.Length; i++)
            {
                if (numArray[i] != sortedNumArray[i])
                {
                    var temp = numArray[i];
    
                    numArray[i] = sortedNumArray[i];
    
                    numArray[numAndIndex[numArray[i]]] = temp;
                    break;
                }
            }
    
            return int.Parse(new string(numArray));
        }
    }
    

  • 0

    @bacon I think your solution is more optimal since it is just O(NlogN) while @shawngao's is O(n^2).


  • 0
    B

    @BatCoder Yeah, but it takes more space.


  • 0

    @bacon I agree, but between time and space, I would be ready to compromise more space than time. :)


Log in to reply
 

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