Giới thiệu

Trong bài viết này, chúng ta sẽ tìm hiểu cách xử lý một mảng số nguyên đã được sắp xếp theo thứ tự không giảm. Mục tiêu là loại bỏ các phần tử trùng lặp sao cho mỗi phần tử duy nhất chỉ xuất hiện tối đa hai lần trong mảng. Quá trình này cần được thực hiện tại chỗ mà không làm thay đổi thứ tự của các phần tử. Sau khi hoàn thành, chúng ta sẽ trả về số lượng các phần tử duy nhất còn lại.

Bài toán

Cho một mảng số nguyên nums được sắp xếp theo thứ tự không giảm. Yêu cầu đặt ra là loại bỏ các phần tử trùng lặp sao cho mỗi phần tử chỉ xuất hiện tối đa hai lần. Thứ tự các phần tử trong mảng phải được giữ nguyên. Cuối cùng, chúng ta sẽ trả về k, trong đó k là số lượng phần tử duy nhất sau khi đã loại bỏ các phần tử thừa. Dưới đây là một ví dụ minh họa:

Ví dụ:

• Input: nums = [1, 1, 1, 2, 2, 3]
• Output: 5, nums = [1, 1, 2, 2, 3, _]

Cách giải quyết

Để giải quyết bài toán này, chúng ta sẽ áp dụng kỹ thuật 2 pointers. Cụ thể:

• wp (writer pointer): con trỏ ghi, chỉ vị trí tiếp theo sẽ được ghi vào mảng.
• rp (read pointer): con trỏ đọc, dùng để quét mảng và tìm kiếm các phần tử thỏa mãn điều kiện.

Cách thực hiện:

Chúng ta sẽ quét từ vị trí thứ 2 của mảng cho đến cuối. Nếu nums[wp-2] khác nums[rp], điều đó có nghĩa là phần tử này không bị trùng lặp nhiều hơn 2 lần so với phần tử trước đó (tối đa 2 lần). Khi xác định được như vậy, chúng ta sẽ ghi phần tử vào mảng và tăng chỉ số của writer pointer lên 1.

Thuật toán

Dưới đây là mã nguồn Python cho thuật toán:

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return len(nums)

        wp = 2  # Luôn giữ 2 phần tử đầu tiên
        for rp in range(2, len(nums)):
            if nums[wp-2] != nums[rp]:
                nums[wp] = nums[rp]
                wp += 1

        return wp

Kết luận

Bài toán loại bỏ các phần tử trùng lặp trong mảng đã sắp xếp nhưng chỉ giữ tối đa 2 lần xuất hiện không chỉ giúp chúng ta cải thiện không gian lưu trữ mà còn tăng hiệu suất khi làm việc với mảng. Hy vọng hướng dẫn này giúp bạn hiểu rõ hơn về cách thực hiện giải thuật một cách hiệu quả.
source: viblo