To solve this problem, we need to remove duplicates from a list of integers while preserving the original order of elements. Additionally, we must ensure that the original list remains unmodified.
Approach
The key insight here is to use a set to keep track of elements we have already encountered and a list to build the result. Here's the step-by-step approach:
- Initialize a set: This set will store elements we've seen to allow O(1) average-time complexity for membership checks.
- Initialize a result list: This list will hold the elements in their original order without duplicates.
- Iterate through the input list: For each element, if it hasn't been seen before, add it to both the set and the result list.
- Return the result list: This list contains the unique elements in their original order.
Solution Code
def removeDuplicates(lst):
seen = set()
result = []
for num in lst:
if num not in seen:
seen.add(num)
result.append(num)
return result
Explanation
- Set for Tracking: The set
seenis used to quickly check if an element has already been added to the result list. This ensures that we don't add duplicates. - Result List: The
resultlist is built by appending elements only if they haven't been seen before, thus preserving the original order. - Original List Preservation: Since we are creating a new list (
result) instead of modifying the input list (lst), the original list remains unchanged.
This approach has an average time complexity of O(n) (where n is the number of elements in the input list) because each membership check and insertion into the set takes O(1) average time. The space complexity is O(n) in the worst case (when there are no duplicates), as we need to store all elements in both the set and the result list.
Example Usage:
- Input:
[1, 2, 2, 3, 4, 4, 4, 5]→ Output:[1, 2, 3, 4, 5] - Input:
[5, 3, 5, 2, 3, 3, 9, 0, 123]→ Output:[5, 3, 2, 9, 0, 123] - Input:
[]→ Output:[] - Input:
[2, 2, 2]→ Output:[2]
This solution efficiently handles all edge cases and meets the problem requirements.


作者声明:本文包含人工智能生成内容。