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]
Runtime: 4 ms, faster than 86.08% of C++ online submissions for Maximum Swap.
//
// Created by yuxi on 2019-01-18.
//
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std; class Solution {
private:
unordered_map<int,vector<int>> mp;
public:
int getret(vector<int>& a){
int ret = ;
for(int i=; i<a.size(); i++){
ret = ret * + a[i];
}
return ret;
}
int maximumSwap(int num) {
int savenum = num;
vector<int> numa;
while(num > ){
numa.push_back(num%);
num /= ;
}
reverse(numa.begin(), numa.end());
for(int i=; i<numa.size();i++) mp[numa[i]].push_back(i);
if(numa.size() == ) return numa[];
helper(numa, );
return getret(numa);
}
void helper(vector<int>& a, int idx) {
if(idx == a.size()) return ;
int maxval = INT_MIN, maxidx = ;
for(int i=idx; i<a.size(); i++) {
if(maxval < a[i]) {
maxval = a[i];
maxidx = i;
}
}
if(maxval != a[idx]) {
int tmp = a[idx];
a[idx] = maxval;
a[maxidx] = tmp;
if(mp[maxval].size() != && mp[maxval].back() > maxidx) {
a[mp[maxval].back()] = tmp;
a[maxidx] = maxval;
}
return;
} else {
helper(a, idx+);
}
}
};