การหาความยาวลำดับตัวเลขติดต่อกันที่ยาวที่สุดในอาร์เรย์ด้วย JavaScript

บทความนี้สาธิตการหาความยาว longest consecutive sequence (ไม่จำเป็นต้องติดกันในอาร์เรย์)

ตัวอย่าง

arr = [4, 6, 9, 1, 2, 8, 5, 3, -1]
longest consecutive: 1,2,3,4,5,6 -> length 6

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

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

const consecutiveSequence = (arr = []) => {
  const consecutiveRight = {};
  let max = 0;
  for (let i = 0; i < arr.length; i += 1) {
    let curr = arr[i];
    if (consecutiveRight[curr] !== undefined) {
      continue;
    }
    consecutiveRight[curr] = 1 + (consecutiveRight[curr + 1] || 0);
    while (consecutiveRight[curr - 1] !== undefined) {
      consecutiveRight[curr - 1] = consecutiveRight[curr] + 1;
      curr -= 1;
    }
    max = Math.max(max, consecutiveRight[curr]);
  }
  return max;
};

console.log(consecutiveSequence(arr));

ผลลัพธ์

6

คำอธิบาย

ใช้ hash map เก็บความยาว consecutive sequence เริ่มจากตัวเลขนั้นไปทางขวา

เมื่อเจอตัวเลขใหม่ คำนวณความยาว = 1 + ความยาวของตัวถัดไป แล้ว update ย้อนกลับทางซ้าย

Time: O(n) amortized, Space: O(n)

วิธีทั่วไป: ใช้ Set แล้วหา start ของ sequence (n-1 ไม่อยู่ใน set) นับต่อไป