leetcode
leetcode 701 ~ 750
自定义字符串排序

自定义字符串排序

难度:

标签:

题目描述

代码结果

运行时间: 20 ms, 内存: 0.0 MB


/*
题目思路:
1. 使用 HashMap 存储 order 中字符的顺序。
2. 将 s 字符串转换为流,按顺序和不按顺序分类。
3. 按照 order 中的顺序排序后与未排序部分结合。
*/
import java.util.*;
import java.util.stream.*;

public class CustomSortString {
    public String customSortString(String order, String s) {
        // 存储 order 中字符的顺序
        Map<Character, Integer> orderMap = new HashMap<>();
        for (int i = 0; i < order.length(); i++) {
            orderMap.put(order.charAt(i), i);
        }
        
        // 使用 Java Stream API 处理字符分类和排序
        String result = s.chars()
            .mapToObj(c -> (char) c)
            .sorted(Comparator.comparingInt(c -> orderMap.getOrDefault(c, Integer.MAX_VALUE)))
            .map(String::valueOf)
            .collect(Collectors.joining());
        
        return result;
    }
}

解释

方法:

题解的思路是首先使用collections.Counter统计字符串T中各字符的出现频次。然后,按照字符串S(order)给定的顺序,从计数器中取出相应字符,并构建结果字符串。这确保了S中的字符在结果中的顺序是正确的。如果T中有字符不在S中,这些字符将保留在Counter中。最后,将剩余的字符按其原有频次添加到结果字符串的末尾。这样,S中未提及的字符将按T中的出现顺序排列。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在解决方案中,为什么要使用`collections.Counter`来统计`s`中的字符频率而不是其他数据结构?
`collections.Counter`是Python中用于计数的专门数据结构,它能够以字典形式存储元素及其计数,让频次统计变得更加直接和高效。使用Counter可以简化代码,并自动处理频次的累加,比手动维护字典或数组更为方便。此外,Counter提供了许多便利的方法,如`most_common`和`pop`,可以在算法实现中提供额外的帮助。
🦆
算法在处理不在`order`中但存在于`s`中的字符时,是如何保证这些字符的相对顺序不变的?
算法通过在最终添加剩余字符的步骤中维持`collections.Counter`中的顺序来实现。在Python中,`collections.Counter`遍历时是按照元素首次添加的顺序进行的。因此,对于T中存在但不在S中的字符,在将它们添加到最终结果字符串时,会按照它们在字符串T中出现的顺序来添加,从而保持了相对顺序的一致性。
🦆
代码中使用`ct.pop(s)`而不是`ct[s]`,这样做有什么特别的意图或优势?
使用`ct.pop(s)`的主要优势是在取出元素的同时将其从计数器中移除,这样做可以避免对已经处理过的字符进行重复处理。这不仅清理了数据结构,还减少了后续操作的复杂性,因为我们不需要额外的逻辑来跳过已经添加到结果字符串中的字符。这样的操作使得代码更简洁,逻辑更清晰。
🦆
如果`order`中包含的字符在`s`中并不出现,这种情况是否会影响到最终结果字符串的构建?
如果`order`中的字符在`s`中不出现,这不会影响到最终结果字符串的正确性,但会增加一些无效的操作。在算法中,会遍历`order`中的每个字符并尝试从计数器中移除并添加到结果字符串。如果这些字符在`s`中不存在,那么相应的频次为零,这部分操作实际上是不会对结果字符串产生任何添加。因此,这种情况只是影响了算法的效率,而不影响结果的正确性。

相关问题