0

Remove duplicates in sorted arrays but keep at most 2 same elements

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, hãy loại bỏ một số phần tử trùng lặp trong mảng tại chỗ sao cho mỗi phần tử duy nhất xuất hiện tối đa hai lần. Thứ tự tương đối của các phần tử phải được giữ nguyên. Trả về k sau khi đặt kết quả cuối cùng vào k vị trí đầu tiên của nums.

Ví dụ:

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

Hướng giải quyết

  • Chúng ta sẽ sử dụng 2 pointers trong trường hợp này:

    • wp: writer pointer dùng để chỉ vị trí sắp tới được viết vào mảng
    • rp: read pointer dùng để scan mảng và tìm ra các phần tử phù hợp
  • Chúng ta sẽ scan mảng , bắt đầu tại vị trí thứ 2 cho đến cuối. Nếu nums[wp-2] != nums[rp] tức là phần tử này không bị lặp quá 2 lần so với phần tử trước đó ( xuất hiện tối đa 2 lần) thì sẽ viết vô mảng và tăng write pointer lên 1.

Thuật toán


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

        wp = 2  # always take 0 and 1 element
        for rp in range(2, len(nums)):
            if nums[wp-2] != nums[rp]:
                nums[wp] = nums[rp]
                wp += 1

        return wp

Tham khảo

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/submissions/1530538026/?envType=study-plan-v2&envId=top-interview-150


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.