Remove Duplicates from Sorted Array

+10

Bạn có một mảng số nguyên nums được sắp xếp theo thứ tự không giảm, nên các giá trị bằng nhau nằm cạnh nhau. Hãy trả về các giá trị phân biệt của nums, mỗi giá trị một lần, theo thứ tự xuất hiện. Ví dụ, [2, 2, 5] cho kết quả [2, 5].

Hàm

removeDuplicates(nums: integer-array) → integer-array

numsinteger-array: các số nguyên theo thứ tự không giảm
Trả vềinteger-array: các giá trị riêng biệt của nums, theo thứ tự tăng dần

Ràng buộc

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums được sắp xếp theo thứ tự không giảm.

Ví dụ

Đầu vào: nums = [1, 1, 2, 3, 3, 3]
Đầu ra: [1, 2, 3]
Giải thích: 1 xuất hiện hai lần và 3 xuất hiện ba lần. Giữ lại mỗi giá trị một lần thì còn [1, 2, 3].

Đầu vào: nums = [-2, 0, 0, 5]
Đầu ra: [-2, 0, 5]
Giải thích: Chỉ có 0 lặp lại. Các giá trị âm cũng hoạt động tương tự, vì vậy đáp án là [-2, 0, 5].

Đầu vào: nums = [7, 7, 7]
Đầu ra: [7]
Giải thích: Mọi giá trị đều là 7, nên chỉ còn lại một 7.

Câu hỏi mở rộng

Bạn có thể thực hiện việc này với bộ nhớ phụ O(1) bằng cách ghi đè trực tiếp lên nums thay vì tạo một mảng thứ hai không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Trong một mảng chưa được sắp xếp, bạn sẽ phải ghi nhớ mọi giá trị đã gặp. Việc sắp xếp gom tất cả bản sao của một giá trị thành một nhóm, vì vậy một giá trị là mới khi và chỉ khi nó khác với giá trị cuối cùng bạn đã giữ lại. Chỉ cần duyệt một lượt với chỉ số đọc và chỉ số ghi để xử lý ngay tại chỗ.

Ghi nhớ các giá trị đã gặp trong tập hợp băm

Ý tưởng

Duyệt qua nums và lưu các giá trị đã có trong kết quả vào một tập hợp. Thêm một giá trị khi gặp nó lần đầu, rồi bỏ qua những lần gặp sau, để mỗi giá trị chỉ xuất hiện một lần theo thứ tự bạn gặp chúng. Cách này không dựa vào thứ tự sắp xếp và áp dụng được cho mọi mảng.

Tra cứu trong tập hợp mất trung bình O(1), nên lượt duyệt mất O(n), nhưng tập hợp và kết quả có thể chứa mỗi bên n giá trị: cần thêm O(n) bộ nhớ. Trong C, một mảng cờ dành cho 2 × 10^4 + 1 giá trị có thể thay thế tập hợp.

Thuật toán

Tạo một tập hợp rỗng seen và một danh sách rỗng result.
Với mỗi giá trị trong nums, kiểm tra xem nó có nằm trong seen không.
Nếu không, thêm giá trị đó vào seen và nối nó vào result.
Trả về result.

def removeDuplicates(nums):
    seen = set()
    result = []
    for num in nums:
        if num not in seen:
            seen.add(num)
            result.append(num)
    return result

Nén tại chỗ bằng con trỏ ghi

Ý tưởng

Chỉ số ghi k đánh dấu điểm kết thúc của phần được giữ lại: từ nums[0] đến nums[k-1] luôn chứa các giá trị phân biệt đã tìm thấy cho đến lúc đó, vì vậy nums[k-1] là giá trị cuối cùng được giữ lại. Chỉ số đọc i duyệt qua mọi giá trị. Một giá trị bằng nums[k-1] là một bản sao khác trong dãy liên tiếp mà bạn đã giữ lại; một giá trị khác bắt đầu một dãy mới và được ghi vào nums[k].

Với [1, 1, 2, 3, 3, 3], i = 1 bỏ qua số 1 thứ hai, i = 2 ghi 2 vào chỉ số 1, i = 3 ghi 3 vào chỉ số 2, còn hai số 3 cuối cùng bị bỏ qua. Ba vị trí đầu tiên chứa [1, 2, 3].

Vì k không bao giờ vượt quá i, thao tác ghi không bao giờ ghi đè lên giá trị bạn chưa đọc. Lượt duyệt mất thời gian O(n) và dùng thêm hai số nguyên làm bộ nhớ phụ.

Thuật toán

Đặt k = 1: luôn giữ lại nums[0].
Lặp i từ 1 đến chỉ số cuối cùng.
Nếu nums[i] khác nums[k-1], đặt nums[k] = nums[i] rồi tăng k thêm 1.
Trả về nums với k giá trị đầu tiên.

def removeDuplicates(nums):
    # nums[0:k] holds the distinct values found so far, in order.
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return nums[:k]

Lỗi thường gặp và trường hợp biên

So sánh nums[i] với nums[i+1] khi i chạy đến chỉ số cuối cùng. Lần so sánh cuối cùng đọc vượt quá phần tử cuối.
Bắt đầu k từ 0. Khi đó, giá trị đầu tiên được so sánh với nums[-1], chỉ số này nằm ngoài phạm vi hoặc, trong Python, trỏ đến phần tử cuối cùng.
Trả về toàn bộ mảng thay vì chỉ trả về k giá trị đầu tiên. Phần cuối vẫn giữ các giá trị cũ, nên [1, 1, 2] trở thành [1, 2, 2].
Tạo kết quả bằng cách lặp qua một tập hợp băm. Hầu hết các tập hợp băm không giữ thứ tự, nên các giá trị có thể bị xáo trộn.
Trong Lua và R, mảng bắt đầu từ 1. Phần được giữ lại là từ nums[1] đến nums[k], và bạn so sánh với nums[k].

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán Xóa phần tử trùng lặp khỏi mảng đã sắp xếp là bao nhiêu?

Giải pháp dùng con trỏ ghi đọc mỗi giá trị một lần, nên chạy trong thời gian O(n). Ngoài các giá trị được trả về, giải pháp này dùng O(1) không gian bổ sung: hai chỉ số.

Tại sao mảng cần được sắp xếp?

Sắp xếp đưa mọi bản sao của một giá trị vào cùng một nhóm liên tiếp, nên chỉ cần so sánh với giá trị được giữ lại gần nhất. Trong một mảng chưa được sắp xếp, bản sao có thể xuất hiện ở bất kỳ đâu, nên bạn cần một tập hợp băm chứa mọi giá trị đã gặp, tốn thêm O(n) bộ nhớ.

Bạn sẽ cho phép mỗi giá trị xuất hiện nhiều nhất hai lần như thế nào?

So sánh với giá trị cách hai vị trí trong phần được giữ lại thay vì một vị trí: sao chép nums[i] khi k < 2 hoặc khi nó khác nums[k-2]. Nếu nó bằng nums[k-2], phần được giữ lại đã kết thúc bằng hai bản sao của giá trị đó. Cùng ý tưởng này cho phép giữ lại tối đa m bản sao bằng cách dùng nums[k-m].

def removeDuplicates(nums):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [1, 1, 2, 3, 3, 3]

Đầu ra mong đợi

[1, 2, 3]