[Math_Medium]670.Maximum Swap

原题：670.Maximum Swap

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.
2. Input: 9973
   Output: 9973
   Explanation: No swap.

题目大意

给你一个非负数，你最多只能把其中的2个数字进行对调，请求出进行操作后所得到的最大值

解题思路

开始我想错了，自以为地想只要把最大数字和最高位数字进行对调就可以了，却忽略了当最大数字已经在最高位时，我们应该确保次高位数字最大 ，或当最高位和次高位均已经为最大时，应该保证第三位最大。
因此，咱们可以先把每个数字进行排序，再与原来的数字从最高位开始进行比较，找到第一个不同位，然后确保在从第一个不同位开始以及后面的位中，取出最大的那一位与第一个不同位进行对调，即可

代码如下：

class Solution {
public:
    int maximumSwap(int num) 
    {
        int temp_num=num;
        int a_i=0,b_i=0,i=0;
        int a[10]={0},b[10]={0};
        while(temp_num)
        {
            a[a_i++]=temp_num%10;
            b[b_i++]=temp_num%10;
            temp_num/=10;
        }
        sort(b,b+b_i);
        for(i=a_i-1;i>=0;i--)
        {
            if(a[i]!=b[i])//找到第一个不相同的位
                break;
        }
        int j=0,max_num=i;
        for(j=i;j>=0;j--)
        {
            if(a[j]>=a[max_num])//从这一位开始往后面找最大的数，用>=，即如果有两个
                max_num=j;//相同的数，把低位上的提上来，使得值最大，1993，应该把十位上的9提到前面
        }
        if(i>=0)
        {
            int tmp=a[i];
            a[i]=a[max_num];
            a[max_num]=tmp;
        }
        int ans=0;
        for(i=a_i;i>=0;i--)
        {
            ans=(ans*10+a[i]);
        }
        return ans;
    }
};