Python字符频率排序优化咨询：频率降序+同频字典序升序

Your initial approach works, but we can cut out the extra find_num_occur function and secondary sorting by using Python's built-in tools more effectively. Here's a much cleaner implementation that meets all your requirements:

from collections import Counter

def string_sort(s):
    # Step 1: Count character frequencies (simplified with Counter)
    char_counts = Counter(s)
    # Step 2: Sort by two criteria in one pass
    # - First: descending frequency (negative count reverses the sort order)
    # - Second: ascending lexicographical order for ties
    sorted_chars = sorted(char_counts.items(), key=lambda x: (-x[1], x[0]))
    # Step 3: Build the final result string
    return ''.join(char * count for char, count in sorted_chars)

How This Works: #

1. Simplified Frequency Counting: collections.Counter is a standard library tool that replaces your manual hash table loop with one line of code. If you prefer avoiding imports, you can still simplify your manual count using dict.get():

   char_counts = {}
   for char in s:
       char_counts[char] = char_counts.get(char, 0) + 1
   

2. Multi-Criteria Sorting: The key parameter in sorted() is the key to simplification here. When you pass a tuple like (-x[1], x[0]), Python sorts by the first tuple element first, then the second:

   • -x[1]: Using the negative frequency turns an ascending sort into a descending one, so higher frequencies appear first.
   • x[0]: For characters with identical frequencies, this sorts them in standard dictionary (lexicographical) order (ascending, which matches your requirement).

   This eliminates the need for your find_num_occur function and secondary sorting loop—sorted() handles both conditions in a single pass.

3. Efficient Result Construction: The generator expression char * count for char, count in sorted_chars builds repeated character sequences efficiently, and ''.join() combines them into the final string cleanly.

Testing Against Your Examples: #

Let’s confirm this works with your test cases:

• bdca → Counts: {'b':1, 'd':1, 'c':1, 'a':1} → Sorted result: a, b, c, d → Output: abcd
• bdcda → Counts: {'d':2, 'b':1, 'c':1, 'a':1} → Sorted result: d, a, b, c → Output: ddabc
• abba → Counts: {'a':2, 'b':2} → Sorted result: a, b → Output: aabb
• bacbdc → Counts: {'b':2, 'c':2, 'a':1, 'd':1} → Sorted result: b, c, a, d → Output: bbccad

All examples match your expected results!

Note on "Comparators" in Python 3: #

You mentioned hearing about comparators—Python 3 removed the old cmp parameter for custom comparator functions. Instead, we use the key parameter (as shown above) which is more efficient. For complex custom sorting scenarios, you could use functools.cmp_to_key() to convert a comparator function into a key function, but for this use case, the tuple key is far simpler and cleaner.

内容的提问来源于stack exchange，提问作者Martin