LeetCode 0041
About 2 min
0041. First Missing Positive
- Thẻ: Mảng, Bảng băm
- Độ khó: Khó
Tóm tắt đề bài
Mô tả: Cho một mảng số nguyên chưa được sắp xếp nums
.
Yêu cầu: Tìm số nguyên dương nhỏ nhất không xuất hiện trong mảng.
Giới hạn:
- .
- .
- Yêu cầu thực hiện với độ phức tạp thời gian và chỉ sử dụng không gian bổ sung cấp số nhân.
Ví dụ:
- Ví dụ 1:
Input: nums = [1,2,0]
Output: 3
- Ví dụ 2:
Input: nums = [3,4,-1,1]
Output: 2
Ý tưởng giải quyết
Ý tưởng 1: Bảng băm, bảng băm trong chính mảng
Nếu sử dụng bảng băm thông thường, chúng ta chỉ cần duyệt qua mảng một lần, lưu trữ các số nguyên tương ứng vào bảng băm và kiểm tra từ 1
trở đi xem số nguyên dương tương ứng có xuất hiện trong bảng băm hay không. Tuy nhiên, phương pháp này có độ phức tạp không gian là , không đáp ứng yêu cầu về không gian bổ sung cấp số nhân.
Chúng ta có thể coi mảng hiện tại như một bảng băm. Một mảng có độ dài n
tương ứng với các giá trị phần tử từ [1, n + 1]
, trong đó còn thiếu một phần tử.
- Chúng ta có thể duyệt qua mảng một lần, đặt phần tử hiện tại vào vị trí tương ứng của nó (ví dụ: phần tử có giá trị
1
đặt vào vị trí thứ0
của mảng, phần tử có giá trị2
đặt vào vị trí thứ1
của mảng, và cứ tiếp tục như vậy). - Sau đó, chúng ta duyệt qua mảng một lần nữa. Nếu gặp phần tử đầu tiên không bằng chỉ số + 1, đó chính là số nguyên dương nhỏ nhất bị thiếu.
- Nếu duyệt qua mảng mà không tìm thấy số nguyên dương bị thiếu, thì số nguyên dương bị thiếu là
n + 1
. - Cuối cùng, chúng ta trả về số nguyên dương bị thiếu mà chúng ta đã tìm thấy.
Ý tưởng 1: Code
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
size = len(nums)
for i in range(size):
while 1 <= nums[i] <= size and nums[i] != nums[nums[i] - 1]:
index1 = i
index2 = nums[i] - 1
nums[index1], nums[index2] = nums[index2], nums[index1]
for i in range(size):
if nums[i] != i + 1:
return i + 1
return size + 1
Ý tưởng 1: Phân tích độ phức tạp
- Độ phức tạp thời gian: , trong đó là số lượng phần tử trong mảng
nums
. - Độ phức tạp không gian: .