如何移除升序列表中与前一元素差值小于指定值的元素

Let's break down how to solve this problem: we have a sorted ascending list, and we need to keep only elements where consecutive entries in the final list have a difference of at least 10.

Approach #

Since the input list is already sorted, we can use a straightforward iterative method:

1. Start with an empty result list. The first element of the input list always gets added (there's nothing to compare it to yet).
2. For each subsequent element, check if its difference from the last element we kept is 10 or more. If yes, add it to the result and update our reference to the last kept element.
3. Skip any elements that don't meet this difference requirement.

Python Implementation #

def filter_min_diff(sorted_list, min_diff):
    if not sorted_list:
        return []
    result = [sorted_list[0]]
    last_retained = sorted_list[0]
    for num in sorted_list[1:]:
        if num - last_retained >= min_diff:
            result.append(num)
            last_retained = num
    return result

# Test with your example input
input_list = [10,15,17,21,34,36,42,67,75,84,92,94,103,115]
filtered_list = filter_min_diff(input_list, 10)
print(filtered_list)  # Output: [10, 21, 34, 67, 84, 94, 115]

Explanation #

• Edge Case Handling: We first check if the input list is empty to avoid errors.
• Initialization: The first element is added to the result because it's our starting point.
• Iteration: We loop through the rest of the list, comparing each element to the last one we kept. If the difference meets our threshold, we add it to the result and update our reference.
• Efficiency: This runs in O(n) time (we only traverse the list once) and uses O(k) space, where k is the length of the filtered list (worst case O(n) if all elements meet the requirement).

Memory-Efficient Alternative (Generator) #

For very large lists, you can use a generator to yield elements on the fly instead of storing the entire result upfront:

def filter_min_diff_gen(sorted_list, min_diff):
    if not sorted_list:
        return
    last_retained = sorted_list[0]
    yield last_retained
    for num in sorted_list[1:]:
        if num - last_retained >= min_diff:
            yield num
            last_retained = num

# Usage
filtered_list = list(filter_min_diff_gen(input_list, 10))
print(filtered_list)  # Same output as before

This is great for processing elements one at a time without loading the entire filtered list into memory.

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