Xóa trùng lặp khỏi mảng đã sắp xếp trong Python

Cho mảng đã sắp xếp A. Trả về độ dài sau khi xóa trùng lặp tại chỗ (O(1) space). Ví dụ: [1,1,2,2,2,3,3,3,3,4,5,5,5,6] → 6.

Giải pháp

Hai con trỏ:

• Nếu rỗng → 0.
• prev = A[0], length=1, index=1.
• Duyệt i=1..n-1: nếu A[i]!=prev → length++, prev=A[i], nums[index]=A[i], index++.
• Trả về length.

Ví dụ

Triển khai Python:

class Solution(object): 
    def removeDuplicates(self, nums): 
        if len(nums) == 0: 
            return 0 
        length = 1 
        previous = nums[0] 
        index = 1 
        for i in range(1,len(nums)): 
            if nums[i] != previous: 
                length += 1 
                previous = nums[i] 
                nums[index] = nums[i] 
                index+=1 
        return length 
input_list = [1,1,2,2,2,3,3,3,3,4,5,5,5,6] 
ob1 = Solution() 
print(ob1.removeDuplicates(input_list))

Đầu vào

[1,1,2,2,2,3,3,3,3,4,5,5,5,6]

Đầu ra

6