查找列表中非重复元素的代码优化求助：小列表正常执行、大集合触发超时错误

Your original code works for small lists but hits timeouts with large datasets because it uses an inefficient nested loop approach—for every unique element, it scans the entire list again to count occurrences, leading to O(n²) time complexity. For large n, this becomes exponentially slow. Let's fix this with a more efficient approach, plus correct the input parsing bug in your original code.

The Issues in the Original Code #

1. O(n²) Time Complexity: Using set(li) to get unique elements, then looping through the entire list for each element to count occurrences is very inefficient for large lists.
2. Incorrect Input Parsing: list(input()) splits the input into individual characters (including spaces), which is not what you want for space-separated values like your test dataset. You need to split on spaces instead.

Optimized Solution Using collections.Counter #

Python's built-in collections.Counter is designed exactly for this scenario—it counts occurrences of elements in a single pass through the list, giving us O(n) time complexity, which is drastically faster for large datasets.

Here's the optimized code:

from collections import Counter

# Correctly parse input into a list of elements (split by spaces)
li = input().split()
# Count occurrences of each element in one pass
element_counts = Counter(li)
# Iterate through the counts to find elements that appear exactly once
for element, count in element_counts.items():
    if count == 1:
        print(element)

How This Works #

1. Input Parsing: input().split() splits the input string into a list of elements using spaces as separators, which fixes the original parsing bug.
2. Efficient Counting: Counter(li) traverses the list once, storing each element's count in a dictionary-like structure. This is a single O(n) operation.
3. Finding Unique Elements: We loop through the key-value pairs in the Counter (O(k) time, where k is the number of unique elements, which is always ≤ n) and print elements with a count of 1.

Alternative: Manual Dictionary Counting (No External Libraries) #

If you prefer not to use collections.Counter, you can achieve the same efficiency with a manual dictionary:

li = input().split()
element_counts = {}

# Count occurrences in one pass
for element in li:
    if element in element_counts:
        element_counts[element] += 1
    else:
        element_counts[element] = 1

# Find and print elements with count 1
for element, count in element_counts.items():
    if count == 1:
        print(element)

This also runs in O(n) time, as we only traverse the list once to build the counts, then once more through the unique elements.

Testing with Your Dataset #

For your test input:
1 2 3 6 5 4 4 2 5 3 6 1 6 5 3 2 4 1 2 5 1 4 3 6 8 4 3 1 5 6 2

Both optimized solutions will correctly output 8, as it's the only element that appears exactly once.

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