ORIGIN

LeetCode 2231. Largest Number After Digit Swaps by Parity

2023-02-04

ACM Heap Priority Queue 1 min142 words

Problem Description

2231. Largest Number After Digit Swaps by Parity

Analysis

This problem can be translated into:

sort the even digits from big to small
sort the odd digits from big to small
combine them in the even odd order according to origin number

Because the digits can be sorted any time, not just once.

Code

class Solution {
public:
    int largestInteger(int num) {
        priority_queue<int> odds, even;
        vector<int> digits;
        while(num) {
            int digit = num % 10;
            if(digit & 1) {
                odds.push(digit);
            }else {
                even.push(digit);
            }
            digits.push_back(digit);
            num /= 10;
        }
        int sum = 0;
        for(int i = digits.size() - 1; i >= 0; i --) {
            sum *= 10;
            if(digits[i] & 1) {
                sum += odds.top();
                odds.pop();
            } else {
                sum += even.top();
                even.pop();
            }
        }
        return sum;
    }
};