หาเอลีเมนต์ที่ปรากฏครั้งเดียวในอาร์เรย์เรียงแล้ว - JavaScript

ในอาร์เรย์ที่ เรียงลำดับแล้ว (Sorted) หาตัวแรกที่ปรากฏเพียงครั้งเดียว

ตัวอย่าง

[2, 2, 3, 3, 3, 5, 5, 6, 7, 8, 9]
→ 6 (ตัวแรกที่ไม่ซ้ำ)

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

const firstNonDuplicate = arr => {
  for (let i = 0; i < arr.length; i++) {
    const isFirst = i === 0 || arr[i] !== arr[i - 1];
    const isLast = i === arr.length - 1 || arr[i] !== arr[i + 1];
    if (isFirst && isLast) return arr[i];
  }
  return false;
};

console.log(firstNonDuplicate([2, 2, 3, 3, 3, 5, 5, 6, 7, 8, 9]));

ผลลัพธ์

6

วิธีแบบ Binary Search (O(log n) - เร็วที่สุดสำหรับข้อมูลใหญ่)

const firstNonDuplicateBS = arr => {
  let left = 0, right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const isFirst = mid === 0 || arr[mid] !== arr[mid - 1];
    const isLast = mid === arr.length - 1 || arr[mid] !== arr[mid + 1];
    
    if (isFirst && isLast) return arr[mid];
    
    // ตัดสินใจไปซ้ายหรือขวา
    if (mid % 2 === 0) {
      if (arr[mid] === arr[mid + 1]) left = mid + 2;
      else right = mid - 1;
    } else {
      if (arr[mid] === arr[mid - 1]) left = mid + 1;
      else right = mid - 2;
    }
  }
  return false;
};

ใช้คุณสมบัติของ Sorted Array: ค่าซ้ำจะอยู่ติดกันเป็นคู่