การนับคู่สมาชิกที่มีค่าเท่ากันแต่ index ต่างกันใน JavaScript

บทความนี้สาธิตการนับจำนวนคู่ (i, j) ที่ i < j และ arr[i] === arr[j]

ตัวอย่าง

arr = [7, 9, 5, 7, 7, 5]
pairs: (7,7) indices (0,3), (0,4), (3,4) และ (5,5) indices (2,5) -> 4 pairs

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

const arr = [7, 9, 5, 7, 7, 5];

const equalPairCount = (arr = []) => {
  if (!arr?.length) {
    return 0;
  }
  const map = {};
  let count = 0;
  arr.forEach((val) => {
    if (map[val]) {
      count += map[val];
    }
    map[val] = map[val] + 1 || 1;
  });
  return count;
};

console.log(equalPairCount(arr));

ผลลัพธ์

4

คำอธิบาย

ใช้ frequency map: เมื่อเจอค่า val ที่เคยมีอยู่ map[val] ครั้ง จะสร้างคู่ใหม่ map[val] คู่ (กับทุกตัวก่อนหน้า) เพิ่มเข้า count แล้วเพิ่ม map[val]++

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

ทางคณิตศาสตร์: สำหรับค่าที่มีความถี่ f จำนวนคู่ = f*(f-1)/2