Remove Duplicates from Sorted Array (Easy)

Bài toán

Tiếp theo chuỗi bài về thuật toán, bài thứ 2 tôi xin giới thiệu là bài Remove Duplicates from Sorted Array

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Tôi xin tóm tắt bài toán như sau:

Cho một dãy số không giảm (a[i+1] ≥ a[i]). Đếm xem có bao nhiêu số khác nhau (ví dụ 1,2,2 thì có 2 chữ số khác nhau là 1 và 2) và đưa ra dãy số bao gồm các số khác nhau lên đầu theo thứ tự. Ví dụ:

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2]

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]

Chú ý : Chúng ta cần sửa giá trị ở biến nums chứ không được tạo mới để phù hợp với bài toán ở LeetCode

Hướng giải quyết

Nhận xét

• Đây là dãy không giảm nên nếu a[i] ≠ a[i-1] thì a[i] là phần tử khác với dãy số a (từ 0 đến i-1)
• Nếu danh sách khác rỗng thì luôn tồn tại ít nhất là 1 phần tử kết quả sau cùng ở nums.

Giải pháp

1. Kiểm tra xem danh sách đầu vào có độ dài bằng 0 hay không. Nếu có, trả về 0 vì không có phần tử nào trong danh sách đó không trùng lặp.
2. Khởi tạo một biến "k" bằng 1, biến này sẽ đếm số lượng phần tử không trùng lặp.
3. Sử dụng một vòng lặp để duyệt qua từng phần tử trong danh sách đầu vào, bắt đầu từ phần tử thứ 2.Trong mỗi vòng lặp, kiểm tra xem phần tử hiện tại có giống với phần tử trước đó hay không. Nếu không, ghi đè phần tử tại vị trí k bằng phần tử hiện tại và tăng biến "k" lên 1.
4. Trả về giá trị của biến "k", đó chính là số lượng phần tử không trùng lặp trong danh sách đầu vào.

Vì thuật toán này chỉ duyệt qua danh sách đầu vào một lần và sử dụng các phép toán cơ bản, nên độ phức tạp của nó là O(n), với n là số lượng phần tử trong danh sách đầu vào.

Chạy thử với nums = [1,1,2,3]

• Bước 1: Kiểm tra nums khác rỗng
• Bước 2: k=1
• Bước 3:
  • Phần tử thứ 2 là a[1] = 1, a[1] = a[0] nên bỏ qua
  • Phần tử thứ 3 là a[2] = 2, a[2] ≠ a[1] nên nums[k]=nums[1]=a[2]=2, k=k+1=2
  • Phần tử thứ 4 là a[3] = 3, a[3] ≠ a[2] nên nums[k]=nums[2]=a[3]=3, k=k+1=3
• Bước 4: Trả về k=3 và lúc này nums=[1,2,3,3] (chỉ quan tâm nums=[1,2,3,_] )

Python Code

from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        k = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                nums[k] = nums[i]
                k += 1
        return k