ตรวจสอบว่าอาร์เรย์มี majority element หรือไม่ - JavaScript

ในอาร์เรย์ตัวเลข สมาชิกใดจะเป็น majority element ถ้าปรากฏมากกว่าครึ่งหนึ่งของความยาวอาร์เรย์

เช่น ความยาวอาร์เรย์ 7 ถ้ามีสมาชิกปรากฏ 4 ครั้งขึ้นไป จะเป็น majority และชัดเจนว่าอาร์เรย์ใดๆ มี majority element ได้สูงสุด 1 ตัว

เราต้องเขียนฟังก์ชันที่รับอาร์เรย์ตัวเลขที่มีค่าซ้ำ และคืนค่า true ถ้ามี majority element, false ถ้าไม่มี

ตัวอย่าง

โค้ดต่อไปนี้เป็นตัวอย่าง (ใช้ Boyer-Moore Voting Algorithm):

const arr = [12, 5, 67, 12, 4, 12, 4, 12, 6, 12, 12];

const isMajority = arr => {
  let maxChar = -Infinity, maxCount = 1;
  // ลูปนี้หา candidate สำหรับ majority element
  for(let i = 0; i < arr.length; i++){
    if(maxChar !== arr[i]){
      if(maxCount === 1){
        maxChar = arr[i];
      }else{
        maxCount--;
      };
    }else{
      maxCount++;
    };
  };
  // ลูปนี้ตรวจสอบว่า candidate จริงๆ เป็น majority หรือไม่
  const count = arr.reduce((acc, val) => maxChar===val ? ++acc : acc, 0);
  return count > arr.length / 2;
};

console.log(isMajority(arr));

ผลลัพธ์

จะแสดงผลในคอนโซลดังนี้:

true