LeetCode（Heap)2231. Largest Number After Digit Swaps by Parity

﹏ヽ暗。殇╰゛Y 2023-09-24 23:46 36阅读 0赞

# 1.问题 #

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num after any number of swaps.

Example 1:

> Input: num = 1234  
> Output: 3412  
> Explanation: Swap the digit 3 with the digit 1, this results in the number 3214.  
> Swap the digit 2 with the digit 4, this results in the number 3412.  
> Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.  
> Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.

Example 2:

> Input: num = 65875  
> Output: 87655  
> Explanation: Swap the digit 8 with the digit 6, this results in the number 85675.  
> Swap the first digit 5 with the digit 7, this results in the number 87655.  
> Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.

Constraints:

*  1 <= num <= 109

# 2. 解题思路 #

## 方法1： ##

>  *  输入的数字 n 转换为字符数组 a，然后依次比较 a 中的每个数字
>  *  如果后面的数字比前面的数字大且它们之间的差是偶数，则将它们交换。
>  *  最后将排序后的字符数组 a 转换回整数并返回。

## 方法2： ##

>  *  采用了一种贪心的策略
>  *  首先统计数字 0-9 中每个数字出现的频率。然后从高位向低位遍历数字，并根据当前数字的奇偶性和之前数字出现的频率来决定新数字的构造方式。
>  *  数字是偶数，选择一个比它大的偶数，从而得到一个更大的数字。当前数字是奇数，选择一个比它大的奇数，从而得到一个更大的数字。具体地，我们从数字 9 开始，逐步向下寻找第一个出现过的奇数，将其作为新数字的当前位。同样地，由于我们尽可能选择一个比当前位大的数字，因此得到的新数字一定是最大的。
>  *  在每次构造新数字时，我们需要将对应数字出现的频率减 1，以确保我们得到的新数字是原数字的一个排列。

## 方法3 ##

>  *  用到了两个优先队列，分别保存奇数位和偶数位的数字。
>  *  首先将给定的数字拆分成单个数字，如果当前数字是奇数，则加入奇数位优先队列中，
>  *  否则加入偶数位优先队列中。接下来重新构造数字，按照从高位到低位的顺序，从奇数位和偶数位优先队列中取出数字，拼接成新的数字。
>  *  最后将新的数字转换为整数返回。

# 3. 代码 #

## 代码1： ##

class Solution {
        
    	public int largestInteger(int n){
        
            char[] a = String.valueOf(n).toCharArray();//1.int转为char数组
            for(int i = 0; i < a.length; i++)//for循环遍历，比较char数组的大小，如果两数相减后除2的余数为0，数字交换
                for(int j = i + 1; j < a.length; j++)
                    if(a[j] > a[i] && (a[j] - a[i]) % 2 == 0){
        
                        char t = a[i];
                        a[i] = a[j];
                        a[j] = t;
                    }
            return Integer.parseInt(new String(a));//3.返回int类型的值
        }
    }

> 解题思路基本相同，不同的地方：  
> 上面的代码存在的问题：  
>  O ( n 2 ) O(n^2) O(n2)，因为它包含了两个嵌套循环。当输入的数字很大时，它的运行时间可能会很长。另外，这段代码也没有处理输入数字为负数的情况。  
> 可以使用快速排序（Quick Sort）或归并排序（Merge Sort）等高效的排序算法，以降低时间复杂度。这样可以将时间复杂度降低到  O ( n log ⁡ n ) O(n\\log n) O(nlogn) 或更低。  
> 由于输入数字可能很大，可以使用 long 类型而不是 int 类型来避免溢出的问题。此外，还需要处理输入数字为负数的情况。  
> 可以使用 Java 内置的 StringBuilder 类来代替字符数组，以便更快地拼接字符串。

class Solution {
        
        public int largestInteger(int n) {
        
            StringBuilder sb = new StringBuilder();
            sb.append(n);
            char[] a = sb.toString().toCharArray();
            for (int i = 0; i < a.length; i++) {
        
                for (int j = i + 1; j < a.length; j++) {
        
                    if (a[j] > a[i] && (a[j] - a[i]) % 2 == 0) {
        
                        char t = a[i];
                        a[i] = a[j];
                        a[j] = t;
                    }
                }
            }
            sb = new StringBuilder();
            sb.append(a);
            return Integer.parseInt(sb.toString());
        }
    }

> 补充：为什么是a\[j\] - a\[i\]) % 2 == 0  
> 例如，假设当前的数字为 4213，我们希望通过交换数字的位置得到一个更大的数字。我们可以找到两个数字  2 2 2 和  4 4 4，它们之间的差是  4 − 2 = 2 × 1 4 - 2 = 2 \\times 1 4−2=2×1，是偶数。因此，我们可以将它们的位置交换，得到数字 4213 -> 4213。再找到两个数字  1 1 1 和  3 3 3，它们之间的差是  3 − 1 = 2 × 1 3 - 1 = 2 \\times 1 3−1=2×1，是偶数。因此，我们可以将它们的位置交换，得到数字 4213 -> 4312。这个数字是原数字 4213 的一个排列，且比原数字要大。

## 代码2： ##

class Solution {
        
        public int largestInteger(int num) {
        
            // 将数字转换成字符数组，方便处理每一位数字
            char[] nums = Integer.toString(num).toCharArray();
            
            // 计算 0 - 9 中每个数字出现的频率
            int[] frequency = new int[10];
            for (int index = 0; index < nums.length; index++) {
        
                frequency[nums[index] - '0']++;
            }
            
            int newNumber = 0;
            int evenIndex = 8; // 对应数字8
            int oddIndex = 9; // 对应数字9
            
            // 从高位向低位遍历数字
            for(int index = 0; index < nums.length; index++) {
        
                // 如果当前索引中数字的奇偶性是偶数
                if(nums[index] % 2 == 0) {
        
                    // 获取非零频率的第一个偶数位
                    while(frequency[evenIndex]==0) {
        
                        evenIndex -= 2;
                    }
                    frequency[evenIndex]--; // 该位数字出现的频率减1
                    newNumber = newNumber*10 + evenIndex; // 构造新数字
                } else {
        
                    // 如果当前索引中数字的奇偶性是奇数
                    // 获取非零频率的第一个奇数位
                    while(frequency[oddIndex]==0) {
        
                        oddIndex -= 2;
                    }
                    frequency[oddIndex]--; // 该位数字出现的频率减1
                    newNumber = newNumber*10 + oddIndex; // 构造新数字
                }
            }
           
            return newNumber; // 返回最大的数字
        }
    }

## 代码3 ##

class Solution {
        
        public int largestInteger(int num) {
        
            PriorityQueue<Integer> opq = new PriorityQueue<>(); // 奇数位数字的优先队列
            PriorityQueue<Integer> epq = new PriorityQueue<>(); // 偶数位数字的优先队列
            int bnum = num; // 保存原始数字
            while(num>0){
         // 将数字拆分成单个数字
                int cur = num%10; // 取出当前数字
                if(cur%2==1){
         // 如果是奇数
                    opq.add(cur); // 放入奇数位数字优先队列中
                }else{
        
                    epq.add(cur); // 否则放入偶数位数字优先队列中
                }
                num /= 10; // 去掉个位数，进入下一轮循环
            }
            StringBuilder sb = new StringBuilder(); // 用于构造新数字的字符串
            num = bnum; // 重新获取原始数字
            while(num>0){
         // 从高位到低位遍历原始数字的每一位
                int cur = num%10; // 取出当前数字
                if(cur%2==1)
                    sb.insert(0, opq.poll()); // 如果是奇数，从奇数位数字优先队列中取出最小值拼接到字符串前面
                else
                    sb.insert(0, epq.poll()); // 如果是偶数，从偶数位数字优先队列中取出最小值拼接到字符串前面
                num /= 10; // 去掉个位数，进入下一轮循环
            }
            return Integer.parseInt(sb.toString()); // 将新数字转换为整数返回
        }
    }