การหาจำนวนเต็มบวกที่เล็กที่สุดที่ไม่มีในอาร์เรย์ใน JavaScript

บทความนี้สาธิตการหา positive integer ที่เล็กที่สุด (เริ่มจาก 1) ที่ไม่ปรากฏในอาร์เรย์

ตัวอย่าง

arr = [4, 2, -1, 0, 3, 9, 1, -5]
// 1,2,3,4 มีในอาร์เรย์ -> output: 5

ตัวอย่างโค้ด

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));

ผลลัพธ์

5

คำอธิบาย

เริ่มจาก 1 ตรวจสอบด้วย indexOf ในอาร์เรย์ หาพบก็เพิ่ม count ไปเรื่อยๆ จนไม่พบ

Time: O(n^2) เนื่องจาก indexOf เป็น O(n) ภายใน while loop

Optimization: ใช้ Set เพื่อ O(1) lookup -> O(n) time, O(n) space

const findSmallestMissingOptimized = (arr) => {
  const set = new Set(arr);
  let i = 1;
  while (set.has(i)) i++;
  return i;
};