Sponsored
Sponsored
The idea is to always try and bring the largest possible digit to the leftmost position if it maximizes the number. For this, we can use a map to record the last occurrence of each digit. By iterating through the number, we can then attempt swapping if any larger digit occurs later.
Time Complexity: O(n), where n is the number of digits in num.
Space Complexity: O(1) as the storage is constant due to limited digit size.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int maximumSwap(int num) {
6 string digits = to_string(num);
7 vector<int> last(10, 0);
8 int n = digits.length();
9
10 for (int i = 0; i < n; i++) {
11 last[digits[i] - '0'] = i;
12 }
13
14 for (int i = 0; i < n; i++) {
15 for (int d = 9; d > digits[i] - '0'; d--) {
16 if (last[d] > i) {
17 swap(digits[i], digits[last[d]]);
18 return stoi(digits);
19 }
20 }
21 }
22 return num;
23}
24
25int main() {
26 int num = 2736;
27 cout << maximumSwap(num) << endl;
28 return 0;
29}This C++ implementation follows the same logic as the C solution, using strings and vectors to map digits to their last occurrences. We then perform a greedy swap to maximize the number.