[DailyCoding] Tìm số nguyên dương thấp nhất không tồn tại trong mảng

Chào các bạn,đây là một bài phỏng vấn thuật toán của Stripe.

Cho một mảng các số nguyên, hãy tìm số nguyên dương đầu tiên còn thiếu trong thời gian tuyến tính và không gian không đổi. Nói cách khác, tìm số nguyên dương thấp nhất không tồn tại trong mảng. Mảng cũng có thể chứa các số trùng lặp và số âm.

Ví dụ:

Đầu vào [3, 4, -1, 1] sẽ cho 2.

Đầu vào [1, 2, 0] sẽ cho 3.

Bạn có thể sửa đổi mảng đầu vào tại chỗ

Solution:

Đề bài tìm số nguyên dương nhỏ nhất, số nguyên dương nhỏ nhất là 1, nên mình loop qua mảng để lấy ra tất cả số nguyên dương và đưa vào Map, sau đó chạy từ 1 -> n, nếu tìm được số n+1 không nằm trong Map thì mình return luôn. Mình xin share lại lời giải của bạn Lý Nhân ở comment: