Tìm số nguyên dương nhỏ nhất không có trong mảng trong JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào mảng số nguyên làm đối số đầu tiên và duy nhất.

Hàm của chúng ta nên tìm và trả về số nguyên dương nhỏ nhất không có trong mảng.

Ví dụ:

Nếu mảng đầu vào là:

const arr = [4, 2, -1, 0, 3, 9, 1, -5];

Thì đầu ra nên là:

const output = 5;

vì 1, 2, 3, 4 đã có trong mảng và 5 là số nguyên dương nhỏ nhất vắng mặt.

Ví dụ

Dưới đây là mã nguồn:

const arr = [4, 2, -1, 0, 3, 9, 1, -5]; const findSmallestMissing = (arr = []) => {    let count = 1;    if(!arr?.length){       return count;    };    while(arr.indexOf(count) !== -1){       count++;    };    return count; }; console.log(findSmallestMissing(arr));

Kết quả

Đầu ra trên console:

5

Lưu ý: Code dùng indexOf trong vòng lặp → O(n²) worst case. Tối ưu: dùng Set O(n) time/space, hoặc cyclic sort O(n) time O(1) space (đặt số x tại index x-1).