সোর্টেড অ্যারে থেকে একবার আসা উপাদান বের করা - JavaScript

সোর্টেড অ্যারে থেকে প্রথম নন-ডুপ্লিকেট (শুধু একবার আসা) উপাদান বের করা।

উদাহরণ

[2, 2, 3, 3, 3, 5, 5, 6, 7, 8, 9]
// ২: ২বার, ৩: ৩বার, ৫: ২বার, ৬: ১বার ← প্রথম একবার আসা
// ফলাফল: 6

সমাধান (O(n) - সোর্টেড অ্যারের সুবিধা নেওয়া)

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
console.log(firstNonDuplicate([1, 1, 2, 2, 3, 3]));                // false
console.log(firstNonDuplicate([1, 2, 3, 4, 5]));                   // 1
console.log(firstNonDuplicate([1]));                               // 1

বাইনারি সার্চ (O(log n) - যদি একটিই থাকে)

const firstNonDuplicateBinary = (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 (isFirst) {
      // ডুপ্লিকেট শুরু হয়েছে, ডান পাশে যান
      left = mid + 1;
    } else {
      // ডুপ্লিকেটের মাঝপথে, বাম পাশে যান
      right = mid - 1;
    }
  }
  
  return false;
};

ব্যাখ্যা

• সোর্টেড অ্যারে: ডুপ্লিকেটগুলো ক্লাস্টার্ড থাকে
• O(n) লিনিয়ার স্ক্যান: সহজ এবং সাধারণ ক্ষেত্রে যথেষ্ট
• O(log n) বাইনারি সার্চ: বড় অ্যারে জন্য দ্রুত

উৎপাদন

6