2231. 按奇偶性交换后的最大数字

题目

给你一个正整数 num 。你可以交换 num 中 奇偶性 相同的任意两位数字（即，都是奇数或者偶数）。

返回交换 任意 次之后 num 的 最大 可能值。

示例 1： 输入：num = 1234 输出：3412 解释：交换数字 3 和数字 1 ，结果得到 3214 。 交换数字 2 和数字 4 ，结果得到 3412 。 注意，可能存在其他交换序列，但是可以证明 3412 是最大可能值。 注意，不能交换数字 4 和数字 1 ，因为它们奇偶性不同。

示例 2： 输入：num = 65875 输出：87655 解释：交换数字 8 和数字 6 ，结果得到 85675 。 交换数字 5 和数字 7 ，结果得到 87655 。 注意，可能存在其他交换序列，但是可以证明 87655 是最大可能值。

提示：

• 1 <= num <= 10^9

思路

将按位拆开，分别按奇数和偶数存在中，同时记录偶数的下标，存在一个中。对奇数和偶数进行排序(从小到大)。

最后构造答案，这里从「低位」倒着构造更方便，如果当前下标存在于中，就使用偶数中的一个数，否则使用奇数中的一个数，同时维护两个指针记录两个下一个使用的数。

看了评论区的解法，也可以使用两个优先队列，更简洁一些。另外，可以一开始就转成字符串，就可以在最后构造时直接判断原位是奇数还是偶数，就可以省略掉集合。

代码

class Solution {
    public int largestInteger(int num) {
        // 存储num中为偶数的位
        List<Integer> even = new ArrayList<>();
        // 存储num中为奇数的位
        List<Integer> odd = new ArrayList<>();
        // 存储偶数对应的下标，这里下标是倒着的，即从低位开始数
        Set<Integer> indexOfEven = new HashSet<>();
        int index = 0;
        while (num > 0) {
            int k = num % 10;
            if (k % 2 == 0) {
                even.add(k);
                indexOfEven.add(index);
            } else {
                odd.add(k);
            }
            num /= 10;
            index++;
        }
        Collections.sort(even);
        Collections.sort(odd);
        int ans = 0;
        int p = 0;
        int q = 0;
        // 从低位倒着构造答案，当前下标原来是偶数就从even顺次选，否则就从odd选
        for (int i = 0; i < index; i++) {
            ans += (int) Math.pow(10, i) * (indexOfEven.contains(i) ? even.get(p++) : odd.get(q++));
        }
        return ans;
    }
}