2231. Largest Number After Digit Swaps by Parity

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int largestInteger(int num) {
        vector<int> his(10,0), vec;
        while(num){
            his[num%10]++;
            vec.push_back(num%10);
            num/=10;
        }
        reverse(vec.begin(), vec.end());
        int ret = 0;
        int o = 9, e = 8;
        for(int v:vec){
            if(v&1){
                while(his[o]==0) o-=2;
                his[o]--;
                ret = 10*ret +o;
            }
            else{
                while(his[e] ==0) e-=2;
                his[e]--;
                ret = 10*ret + e;
            }
        }
        
        return ret;
        
    }
};

analysis

  • time complexity O(n)
  • space complexity O(n)