关于O(n+k)时间复杂度查找恰好出现三次三元组的技术问询

Hey there! Let's tackle your two questions one by one—first your time complexity intuition, then the issues with your current code.

1. Is your understanding of O(n+k) time complexity correct? #

Absolutely spot-on! When we talk about O(n+k) time complexity, we’re focusing on the dominant term between n (the length of your input list) and k (the upper bound of your list’s elements):

• If k is far larger than n (e.g., k=10^5 and n=100), the n term becomes negligible, so overall complexity simplifies to O(k).
• If n is far larger than k (e.g., n=10^5 and k=100), the k term is negligible, so we call it O(n).
• When they’re in a similar range, we stick with O(n+k).

Your reasoning here is totally correct!

2. Does the in operation break the intended time complexity? #

Unfortunately, yes—your current code doesn’t actually run in O(n+k) time, and the in and remove operations are the culprit. Here’s why:

• Python’s list in check runs in O(n) time every time you call it, since it has to scan the entire list to find the element.
• The list.remove() method also runs in O(n) time, because after locating the element, it has to shift all subsequent elements left by one position.

In your code, you loop k times, and each iteration could trigger up to 3 in checks and 3 remove calls. That pushes your total time complexity to O(k*n), which is way slower than the intended O(n+k) (especially when both k and n are large).

A Fix for True O(n+k) Time Complexity #

Since your elements are constrained to 0 to k-1, we can use a counting array to track occurrences efficiently. Here’s the approach:

1. First, iterate through your input list once to count how many times each number appears (O(n) time).
2. Then, iterate through the counting array (O(k) time) to collect numbers that appear exactly 3 times, adding each one three times to your result.

Here’s the Python code for this solution:

def find_exact_triplets(lst, k):
    # Initialize count array with zeros (size k, matching element range 0 to k-1)
    count = [0] * k
    for num in lst:
        count[num] += 1
    
    triplets = []
    for num in range(k):
        if count[num] == 3:
            # Add the number three times to the result list
            triplets.extend([num, num, num])
    return triplets

This code strictly adheres to O(n+k) time: the first loop runs in O(n) time, the second in O(k) time, and combining them gives us the desired efficiency.

Quick Test Example #

If lst = [1, 2, 1, 2, 1, 3, 4, 4, 4] and k = 5, the function returns [1,1,1,4,4,4]—exactly the numbers that appear exactly three times.

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