การสร้างอาร์เรย์จำนวนสมาชิกน้อยกว่าตามอาร์เรย์อินพุตใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ตัวเลข ฟังก์ชันควรสร้างอาร์เรย์ผลลัพธ์จากอาร์เรย์อินพุต สำหรับแต่ละสมาชิกที่ตรงกัน อาร์เรย์ผลลัพธ์ควรมีจำนวนของตัวเลขที่น้อยกว่าตัวเลขนั้นทางขวา สุดท้ายคืนค่าอาร์เรย์นี้

ตัวอย่าง

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

const arr = [6, 2, 8, 5, 1, 3];
const buildSmallerArray = (arr = []) => {
  let count;
  let base;
  const res = [];
  for (let i = 0; i < arr.length; i++) {
    base = arr[i];
    count = 0;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < base) count++;
    }
    res.push(count);
  }
  return res;
};
console.log(buildSmallerArray(arr));

ผลลัพธ์

[ 4, 1, 3, 2, 0, 0 ]

คำอธิบายเพิ่มเติม

สำหรับแต่ละ i นับ j>i ที่ arr[j] < arr[i]: 6→{2,5,1,3}=4, 2→{1}=1, 8→{5,1,3}=3, 5→{1,3}=2, 1→{}=0, 3→{}=0 นี่คือ "count of smaller elements to the right" ปัญหาคลาสสิก สามารถทำ O(n log n) ด้วย BST หรือ BIT