First Missing Positive

+10

Bạn có một mảng số nguyên nums chưa được sắp xếp. Hãy trả về số nguyên dương nhỏ nhất (từ 1 trở lên) không xuất hiện trong nums. Mảng có thể chứa số âm, số 0, các giá trị lặp lại và những giá trị lớn hơn nhiều so với độ dài của mảng.

Hàm

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: các số nguyên chưa được sắp xếp, có thể bị lặp lại và có thể là số âm, số không hoặc số rất lớn
Trả vềinteger: số nguyên dương nhỏ nhất còn thiếu trong nums

Ràng buộc

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Các giá trị không theo thứ tự cụ thể nào và có thể lặp lại.

Ví dụ

Đầu vào: nums = [5, -2, 1, 3, 2, 9]
Đầu ra: 4
Giải thích: 1, 2 và 3 đều có trong mảng, còn 4 thì không, nên đáp án là 4. 5 và 9 không quan trọng khi đã thiếu một giá trị nhỏ hơn.

Câu hỏi mở rộng

Bạn có thể tìm câu trả lời trong thời gian O(n) và chỉ dùng thêm O(1) bộ nhớ 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

Sắp xếp tốn thời gian O(n log n), còn tập hợp băm tốn thêm O(n) bộ nhớ. Ta có thể dùng một giới hạn để tốt hơn cả hai cách: n giá trị chỉ bao phủ tối đa n số trong khoảng từ 1 đến n+1, nên đáp án nhiều nhất là n+1. Chỉ các giá trị từ 1 đến n mới quan trọng, và mảng có n ô để ghi nhận chúng, nên bộ nhớ bổ sung giảm xuống O(1).

Thử từng ứng viên bằng cách quét toàn bộ

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Kiểm tra lần lượt các ứng viên 1, 2, 3, ... Với mỗi ứng viên, quét toàn bộ mảng rồi trả về ứng viên đầu tiên mà lần quét không tìm thấy. Theo giới hạn, bạn không bao giờ kiểm tra vượt quá n+1.

Khi mảng chứa các giá trị từ 1 đến n, trung bình mỗi ứng viên được tìm thấy sau khi quét được một nửa mảng, vì vậy với n = 10^4, cần khoảng n²/2 = 5 × 10^7 phép so sánh.

Thuật toán

Đặt candidate thành 1.
Duyệt nums để tìm phần tử bằng candidate, dừng lại ở phần tử đầu tiên.
Nếu không có phần tử nào khớp, hãy trả về candidate.
Nếu có, hãy cộng 1 vào candidate rồi duyệt lại. Bạn không bao giờ vượt quá n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # n values cannot cover all of 1..n+1, so one of these candidates is missing
    for candidate in range(1, n + 2):
        found = False
        for num in nums:
            if num == candidate:
                found = True
                break
        if not found:
            return candidate

Đánh dấu các giá trị từ 1 đến n trong một mảng cờ

Ý tưởng

Vì đáp án tối đa là n+1, hãy bỏ qua mọi giá trị nhỏ hơn 1 hoặc lớn hơn n. Một mảng boolean present có độ dài n+1 ghi lại các giá trị còn lại, nên giá trị như 10^9 không bao giờ được lưu. Trả về v đầu tiên từ 1 đến n có cờ là false, hoặc n+1 nếu tất cả các cờ đều được bật.

Trong ví dụ đầu tiên, n = 6: các cờ của 1, 2, 3 và 5 được bật, -2 và 9 bị bỏ qua, và cờ đầu tiên chưa được bật là 4. Hai lượt duyệt tuyến tính có độ phức tạp thời gian O(n), còn các cờ cần O(n) bộ nhớ.

Thuật toán

Tạo present gồm n+1 cờ được đặt thành false.
Với mỗi giá trị v trong nums thỏa mãn 1 ≤ v ≤ n, đặt present[v] thành true.
Trả về giá trị v đầu tiên từ 1 đến n có cờ là false.
Nếu không có giá trị nào như vậy, trả về n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # present[v] says whether v is in nums; only 1..n can matter
    present = [False] * (n + 1)
    for num in nums:
        if 1 <= num <= n:
            present[num] = True
    for v in range(1, n + 1):
        if not present[v]:
            return v
    return n + 1

Đặt mỗi giá trị vào một ô riêng

Ý tưởng

Giá trị v thuộc về chỉ số v-1. Khi mọi giá trị từ 1 đến n đều ở đúng vị trí, chỉ số đầu tiên i không chứa i+1 chính là đáp án.

Ở mỗi chỉ số, hãy đổi chỗ giá trị về đúng vị trí của nó khi giá trị đó nằm trong khoảng từ 1 đến n và vị trí cần đến chưa chứa giá trị đó. Giá trị được đưa về có thể cũng cần được chuyển đi. Kiểm tra vị trí cần đến chứ không phải i sẽ ngăn các giá trị trùng lặp: trong [1, 1], số 1 thứ hai thấy số 1 ở chỉ số 0 nên vẫn ở nguyên vị trí.

Trong ví dụ đầu tiên, chỉ số 0 đưa số 5 về đúng vị trí, rồi đến số 2 được đưa về; sau đó số 1 và số 3 cũng về đúng vị trí, để lại [1, 2, 3, -2, 5, 9]: chỉ số 3 là vị trí đầu tiên không đúng, nên đáp án là 4.

Mỗi lần đổi chỗ sẽ đưa một giá trị về đúng vị trí của nó mãi mãi, nên các vòng lặp bên trong thực hiện tối đa n lần đổi chỗ tổng cộng: thời gian O(n) và bộ nhớ O(1), ngoại trừ trong R, vì ngôn ngữ này sao chép vector mà nó thay đổi.

Thuật toán

Với mỗi chỉ số i từ 0 đến n-1:
Trong khi 1 ≤ nums[i] ≤ n và nums[nums[i]-1] ≠ nums[i], hãy hoán đổi nums[i] với nums[nums[i]-1].
Sau lượt sắp xếp, tìm chỉ số đầu tiên i sao cho nums[i] ≠ i+1 rồi trả về i+1.
Nếu mọi vị trí đều chứa đúng giá trị tương ứng, hãy trả về n+1.

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        # Keep swapping until slot i holds a value that has no slot or is already home
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            home = nums[i] - 1
            nums[i], nums[home] = nums[home], nums[i]
    # The first slot that does not hold its own value names the answer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

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

Dừng việc hoán đổi khi nums[i] == i+1 thay vì khi vị trí chứa giá trị đó. Với [1, 1], hai số 1 sẽ hoán đổi mãi mãi.
Dùng if thay vì while để hoán đổi. Trong ví dụ đầu tiên, số 2 quay lại từ chỉ số 4 sẽ không bao giờ đến chỉ số 1, và bạn trả về 2 thay vì 4.
Viết nums[i] = nums[nums[i]-1] rồi lại dùng nums[i] làm chỉ số, khiến chương trình đọc vị trí chứa giá trị đó sau khi vị trí này đã thay đổi. Hãy lưu chỉ số của vị trí chứa giá trị đó trước.
Bỏ qua bước kiểm tra phạm vi, khiến 0, -2 hoặc 10^9 được dùng làm chỉ số nằm ngoài mảng.
Trả về n khi mọi vị trí đều đúng. Với [4, 2, 1, 3], đáp án là 5.

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

Độ phức tạp thời gian của First Missing Positive là bao nhiêu?

Lời giải sắp xếp chạy trong thời gian O(n) và dùng thêm O(1) bộ nhớ. Vòng lặp while nằm bên trong vòng lặp for, nhưng mỗi lần hoán đổi sẽ đặt một giá trị vào đúng chỉ số cuối cùng của nó, vì vậy toàn bộ quá trình thực hiện nhiều nhất n lần hoán đổi. Phiên bản dùng mảng cờ chạy trong thời gian O(n) và dùng O(n) bộ nhớ, còn việc quét từng ứng viên chạy trong thời gian O(n²).

Tại sao đáp án không bao giờ lớn hơn n+1?

Các số từ 1 đến n+1 là n+1 giá trị khác nhau, còn mảng có độ dài n chỉ chứa tối đa n giá trị khác nhau, nên sẽ thiếu một giá trị. Đáp án là n+1 khi và chỉ khi mảng chứa mọi giá trị từ 1 đến n.

Giải pháp tại chỗ có làm thay đổi mảng đầu vào không?

Đúng, nó sắp xếp lại các giá trị. Nếu hàm gọi cần giữ nguyên thứ tự ban đầu, hãy sao chép mảng trước, việc này khiến bộ nhớ bổ sung tăng trở lại thành O(n). Một phương pháp khác thực hiện ngay trên mảng thay thế mọi giá trị nằm ngoài khoảng từ 1 đến n bằng n+1, sau đó đánh dấu v là có mặt bằng cách đổi dấu của nums[v-1]; phương pháp này cũng làm thay đổi mảng.

def firstMissingPositive(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [5, -2, 1, 3, 2, 9]

Đầu ra mong đợi

First Missing Positive

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Thử từng ứng viên bằng cách quét toàn bộ

Đánh dấu các giá trị từ 1 đến n trong một mảng cờ

Đặt mỗi giá trị vào một ô riêng

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

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

Bài tập tương tự