【leetcode】670 最大交换（数组）

题目链接：https://leetcode-cn.com/problems/maximum-swap/

题目描述

思路

1 将较大的数尽可能排前面

复杂度分析 时间复杂度：O（n^2） 空间复杂度：O（n）

class Solution { public: int maximumSwap(int num) { string s = to_string(num); // 从前往后遍历，遇到的第一个交换是最大交换 for(int i = 0; i < s.size() - 1; i++){ int index = i; for(int j = i+1; j < s.size(); j++){ if(s[j] >= s[index]) // 此处不能为> 要尽可能将后面的数交换到前面 index = j; } // 存在更大元素 if (index != i && s[index]!= s[i]){ swap(s[i], s[index]); break; } } return stoi(s); } };

2 排序

（1）先得到排序后的字符串s_sort（逆序） （2）从前到后比较s和sort，找到第一个不同的位置i，其中s[i]!=s_sort[i]，设char c = s_sort[i] （3）从后往前遍历s[j]，找到s[j] == c，交换s[i]和s[j]即得到一次交换的最大值

复杂度分析 时间复杂度：O（n log n） 空间复杂度：O（n）

class Solution { public: int maximumSwap(int num) { string s = to_string(num); string s_sort = s; sort(s_sort.begin(), s_sort.end(),greater<char>()); // 从前往后遍历，遇到的第一个交换是最大交换 for(int i = 0; i < s.size()-1 ; i++){ if (s_sort[i] == s[i]) continue; // 找到该数字 char c = s_sort[i]; int j = s.size() -1; while(j> i){ if(c == s[j]) break; --j; } swap(s[i], s[j]); break; } return stoi(s); } };