Python中对排序后相邻相同字符串元素分组（要求O(NC)复杂度）

Since your list is already sorted by the string value, we can solve this with a straightforward linear traversal—no need for extra sorting or complex data structures, which keeps the time complexity right where you need it.

Core Idea #

Because identical strings are guaranteed to be adjacent (thanks to the pre-sorted list), we just need to:

• Track a "current group" as we iterate through the list
• For each element, check if its string matches the string of the current group
  • If yes: add the element to the current group
  • If no: finalize the current group, add it to the result, and start a new group with the current element
• Don't forget to add the last group to the result after the loop ends!

Code Implementation (Python) #

Here's a concrete implementation tailored to your input structure:

def group_adjacent_same_strings(sorted_list):
    # Handle empty input edge case
    if not sorted_list:
        return []
    
    result = []
    # Initialize current group with the first element
    current_group = [sorted_list[0]]
    # Grab the target string (your input has strings wrapped in single-element lists)
    current_target_str = sorted_list[0][1][0]
    
    for item in sorted_list[1:]:
        current_item_str = item[1][0]
        # Compare strings (this is the O(C) part, where C is string length)
        if current_item_str == current_target_str:
            current_group.append(item)
        else:
            # Push the finished group to result
            result.append(current_group)
            # Start new group
            current_group = [item]
            current_target_str = current_item_str
    
    # Add the last remaining group to the result
    result.append(current_group)
    return result

# Test with your input
input_list = [ [2, ["00_01_02"]], [1, ["00_03_04"]], [3, ["00_03_04"]], [6, ["00_03_04"]], [4, ["01_02_03"]], [5, ["01_02_03"]] ]
print(group_adjacent_same_strings(input_list))

Complexity Analysis #

• Time Complexity: O(NC)
  • We traverse the list exactly once: O(N) where N is the number of elements
  • Each string comparison takes O(C) time, where C is the length of the strings
  • Multiplying these gives us the desired O(NC) total time
• Space Complexity: O(N) (for storing the result) — we don't use any extra space beyond the result and a few tracking variables.

Quick Notes #

• If your input structure ever changes (e.g., strings aren't wrapped in single-element lists), just adjust the current_target_str and current_item_str lines to access the string directly.
• This approach works perfectly because the input is pre-sorted—if it weren't, we'd need to sort first (adding O(N log N * C) time), but since you mentioned it's already sorted, we get to skip that step!

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