Bài 26 Leetcode: Remove Duplicates from Sorted Array

Đề bài:

Cho một mảng số nguyên `nums` được sắp xếp theo thứ tự không giảm, loại bỏ các phần tử trùng nhau trong mảng sao cho mỗi phần tử duy nhất chỉ xuất hiện một lần. Thứ tự tương đối của các phần tử phải được giữ nguyên. Sau đó, trả về số lượng phần tử duy nhất trong `nums`.

Giả sử số lượng phần tử duy nhất trong `nums` là k, để được chấp nhận, bạn cần thực hiện các bước sau:

1. Thay đổi mảng `nums` sao cho `k` phần tử đầu tiên của `nums` chứa các phần tử duy nhất theo thứ tự xuất hiện ban đầu trong `nums`. Các phần tử còn lại của `nums` không quan trọng cũng như kích thước của `nums`.

2. Trả về `k`.

Trình đánh giá tùy chỉnh:

Trình đánh giá sẽ kiểm tra giải pháp của bạn bằng đoạn mã sau:

int[] nums = [...]; // Mảng đầu vào
int[] expectedNums = [...]; // Kết quả mong đợi với độ dài chính xác

int k = removeDuplicates(nums); // Gọi triển khai của bạn

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}

Nếu tất cả các khẳng định đều thành công, thì giải pháp của bạn sẽ được chấp nhận.

Ví dụ 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Giải thích: Hàm của bạn nên trả về k = 2, với hai phần tử đầu tiên của nums lần lượt là 1 và 2.
Các phần tử bên ngoài kết quả trả về k (do đó chúng được đánh dấu dưới dạng gạch dưới) không quan trọng.

Ví dụ 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Giải thích: Hàm của bạn nên trả về k = 5, với năm phần tử đầu tiên của nums lần lượt là 0, 1, 2, 3 và 4.
Các phần tử bên ngoài kết quả trả về k (do đó chúng được đánh dấu dưới dạng gạch dưới) không quan trọng.

Ràng buộc:

  • 1 <= độ dài của nums <= 3 * 10^4
  • -100 <= nums[i] <= 100
  • nums được sắp xếp theo thứ tự không giảm.

Giải thích thuật toán bằng C++

class Solution {
 public:
  int removeDuplicates(vector<int>& nums) {
    int i = 0;

    for (const int num : nums)
      if (i < 1 || num > nums[i - 1])
        nums[i++] = num;

    return i;
  }
};

Đây là một phương thức trong lớp `Solution` được sử dụng để loại bỏ các phần tử trùng nhau trong một vector số nguyên `nums` và trả về số lượng phần tử duy nhất sau khi loại bỏ.

Dưới đây là cách thuật toán hoạt động:

1. Khởi tạo một biến `i` với giá trị ban đầu là 0. Biến này sẽ được sử dụng để theo dõi vị trí hiện tại để ghi lại các phần tử duy nhất trong `nums`.

2. Thực hiện vòng lặp `for` để duyệt qua từng phần tử `num` trong `nums`.

3. Trong mỗi lần lặp, kiểm tra điều kiện: nếu `i` nhỏ hơn 1 (đây là phần tử đầu tiên) hoặc phần tử `num` lớn hơn phần tử trước đó trong `nums[i-1]`, có nghĩa là phần tử `num` là một phần tử duy nhất.

4. Trong trường hợp điều kiện trên đúng, ghi lại phần tử `num` vào vị trí `nums[i]` và tăng giá trị của `i` lên 1.

5. Sau khi kết thúc vòng lặp, giá trị của `i` sẽ là số lượng phần tử duy nhất trong `nums` sau khi loại bỏ các phần tử trùng nhau.

6. Trả về giá trị `i`.

Thuật toán trên hoạt động bằng cách duyệt qua từng phần tử trong `nums` và chỉ ghi lại những phần tử duy nhất theo thứ tự xuất hiện ban đầu. Bằng cách so sánh phần tử hiện tại với phần tử trước đó, ta chỉ ghi lại các phần tử khác nhau vào vị trí mới trong `nums`, đồng thời tăng giá trị của `i` để theo dõi số lượng phần tử duy nhất.

Giải thích thuật toán bằng Java

class Solution {
  public int removeDuplicates(int[] nums) {
    int i = 0;

    for (final int num : nums)
      if (i < 1 || num > nums[i - 1])
        nums[i++] = num;

    return i;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def removeDuplicates(self, nums: List[int]) -> int:
    i = 0

    for num in nums:
      if i < 1 or num > nums[i - 1]:
        nums[i] = num
        i += 1

    return i

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.