Bài 27 Leetcode: Remove Element

Đề bài:

Cho một mảng số nguyên `nums` và một số nguyên `val`, loại bỏ tất cả các lần xuất hiện của `val` trong `nums` ngay tại chỗ. Thứ tự của các phần tử có thể thay đổi. Sau đó, trả về số lượng phần tử trong `nums` không bằng `val`.

Giả sử số lượng phần tử trong `nums` không bằng `val` 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ử không bằng `val`. 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 val = ...; // Giá trị cần loại bỏ
int[] expectedNums = [...]; // Kết quả mong đợi với độ dài chính xác.
// Mảng này đã được sắp xếp và không có giá trị nào bằng val.

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

assert k == expectedNums.length;
sort(nums, 0, k); // Sắp xếp k phần tử đầu tiên của nums
for (int i = 0; i < actualLength; 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 = [3,2,2,3], val = 3
Output: 2, nums = [2,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à 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,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
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 chứa 0, 0, 1, 3 và 4.
Lưu ý rằng năm phần tử có thể được trả về trong bất kỳ thứ tự nào.
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:

  • 0 <= độ dài của nums <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

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

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

    for (const int num : nums)
      if (num != val)
        nums[i++] = num;

    return i;
  }
};

Đây là một phương thức trong lớp `Solution` được sử dụng để loại bỏ tất cả các lần xuất hiện của một giá trị `val` trong một vector số nguyên `nums` và trả về số lượng phần tử còn lại 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ử khác `val` 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 `num` khác `val`, có nghĩa là `num` là một phần tử cần được giữ lại.

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ử còn lại trong `nums` sau khi loại bỏ các lần xuất hiện của `val`.

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 các phần tử khác `val` 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ử còn lại. Các phần tử bị xóa (các lần xuất hiện của `val`) sẽ không được ghi lại và sẽ bị bỏ qua.

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

class Solution {
  public int removeElement(int[] nums, int val) {
    int i = 0;

    for (final int num : nums)
      if (num != val)
        nums[i++] = num;

    return i;
  }
}

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

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

    for num in nums:
      if num != val:
        nums[i] = num
        i += 1

    return i

0 / 5 - (0 Đánh Giá)

Leave a Reply

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

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