Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.
Example 1:
Input: 2736 Output: 7236 Explanation: Swap the number 2 and the number 7.
Example 2:
Input: 9973 Output: 9973 Explanation: No swap.
Note:
- The given number is in the range [0, 108]
1 public class Solution { 2 public int MaximumSwap(int num) { 3 if (num < 10) return num; 4 5 var list = new List<int>(32); 6 7 int tmp = num; 8 while (tmp > 0) 9 { 10 list.Insert(0, tmp % 10); 11 tmp /= 10; 12 } 13 14 var maxRight = new int[list.Count]; 15 var max = list[list.Count - 1]; 16 17 for (int i = maxRight.Length - 1; i >= 0; i--) 18 { 19 maxRight[i] = Math.Max(list[i], max); 20 max = maxRight[i]; 21 } 22 23 for (int i = 0; i < list.Count; i++) 24 { 25 if (list[i] < maxRight[i]) 26 { 27 for (int j = list.Count - 1; j >= 0; j--) 28 { 29 if (list[j] == maxRight[i]) 30 { 31 list[j] = list[i]; 32 list[i] = maxRight[i]; 33 34 return CreateInt(list); 35 } 36 } 37 } 38 } 39 40 return num; 41 } 42 43 private int CreateInt(IList<int> list) 44 { 45 int result = 0; 46 47 for (int i = 0; i < list.Count; i++) 48 { 49 result = result * 10 + list[i]; 50 } 51 52 return result; 53 } 54 }