leetcode
leetcode 1951 ~ 2000
按奇偶性交换后的最大数字

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

难度:

标签:

题目描述

代码结果

运行时间: 25 ms, 内存: 16.0 MB


/*
题目思路:
1. 将数字转换为字符串数组,便于逐位操作。
2. 使用Java Stream API来分离奇数位和偶数位数字,并对它们进行排序,奇数降序,偶数降序。
3. 使用Stream拼接处理后的字符,形成最终结果。
*/
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public int largestInteger(int num) {
        String digits = String.valueOf(num);
        String oddSorted = digits.chars()
                .filter(c -> (c - '0') % 2 != 0)
                .boxed()
                .sorted(Collections.reverseOrder())
                .map(c -> (char)(int)c)
                .map(String::valueOf)
                .collect(Collectors.joining());
        String evenSorted = digits.chars()
                .filter(c -> (c - '0') % 2 == 0)
                .boxed()
                .sorted(Collections.reverseOrder())
                .map(c -> (char)(int)c)
                .map(String::valueOf)
                .collect(Collectors.joining());

        final int[] oddIndex = {0};
        final int[] evenIndex = {0};
        String result = digits.chars()
                .mapToObj(c -> (char) c)
                .map(c -> {
                    if ((c - '0') % 2 == 0) {
                        return evenSorted.charAt(evenIndex[0]++);
                    } else {
                        return oddSorted.charAt(oddIndex[0]++);
                    }
                })
                .map(String::valueOf)
                .collect(Collectors.joining());

        return Integer.parseInt(result);
    }
}

解释

方法:

首先将整数转换为数字列表。随后,分别提取出奇数和偶数位的数字,并对它们进行降序排序。在构建最终结果时,遍历原始数字列表,根据每个数字的奇偶性,从排序后的奇数或偶数列表中取出当前最大值进行替换。这种方式确保了每个位置上的数字是可能的最大值,从而使得整个数字尽可能大。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
算法为什么首先将整数转换为数字列表,而不是直接在整数上进行操作?
直接在整数上操作数字的位置和值相对复杂,因为整数本身是不可变的,无法直接更改其内部的单个数字。通过将整数转换为数字列表,我们可以轻松访问和修改各个位置的数字,从而更灵活地进行排序和重新组合。列表提供了一种直观的方式来处理和交换数字,这对于实现题目要求的数字重新排列至关重要。
🦆
在算法中,对奇数和偶数位的数字进行排序的具体原因是什么?这种排序如何确保了可以获得最大的数字?
对奇数和偶数位的数字进行排序的目的是为了确保在构造最终的整数时,每个位置都能放置可能的最大值。通过对奇数和偶数分别进行降序排序,可以确保每次替换操作都使用当前可用的最大奇数或偶数,从而最大化整个数字的值。这种方法保证了在保持数字原有奇偶性的前提下,每个位置都是该奇偶类别中可能的最大数字,从而构造出最大的整数。
🦆
为什么选择使用列表来存储分离出的奇数和偶数位的数字,有没有考虑过其他数据结构?
使用列表来存储奇数和偶数位的数字是因为列表在这种场景下提供了简单直观的动态数组功能,特别是方便地添加元素和弹出元素。虽然可以考虑使用其他数据结构如堆(优先队列)来自动保持元素的排序状态,但对于本问题,列表足够高效,因为我们只需要进行一次排序和连续的弹出操作,这使得列表成为一个简单且有效的选择。
🦆
算法在替换原始数字列表的元素时,是否保证了每次都取出了当前最大可能的奇数或偶数?
是的,算法确保了每次替换操作都使用当前最大可能的奇数或偶数。这是通过将奇数和偶数列表进行降序排序,并在替换时从对应的列表中顺序弹出最前面的元素实现的。由于排序是降序的,列表的首个元素始终是当前可用的最大值,这保证了每次替换都能使得数字尽可能大。

相关问题