本文共 820 字，大约阅读时间需要 2 分钟。

1. 题目

给定一个非负整数，你至多可以交换一次数字中的任意两位。

示例 1 :输入: 2736输出: 7236解释: 交换数字2和数字7。示例 2 :输入: 9973输出: 9973解释: 不需要交换。注意:给定数字的范围是 [0, 10^8]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-swap

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 逆序求得右边最大数的下标
• 正序找到第一个右边最大的不等于自己的，交换
  

class Solution {
   public:    int maximumSwap(int num) {
       	string s = to_string(num);    	int i, n = s.size(), maxnum = -1, maxid;    	vector
   
     rightMaxidx(n,-1);    	for(i = n-1; i >= 0; --i)    	{
       		if(s[i]-'0' > maxnum)    		{
       			maxnum = s[i]-'0';    			maxid = i;    		}    		rightMaxidx[i] = maxid;    	}    	for(i = 0; i < n; ++i)    	{
       		if(rightMaxidx[i] == i || s[i] == s[rightMaxidx[i]])    			continue;    		swap(s[i],s[rightMaxidx[i]]);    		break;    	}    	return stoi(s);    }};
   

4 ms 6.2 MB

转载地址：https://michael.blog.csdn.net/article/details/106271125 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！