Đếm số nhỏ hơn sau mỗi phần tử trong JavaScript

Mô tả vấn đề

Chúng ta cần viết hàm JavaScript nhận vào mảng số làm đối số duy nhất. Hàm xây dựng mảng mới, mỗi phần tử tương ứng là số lượng phần tử nhỏ hơn nó ở bên phải trong mảng gốc.

Ví dụ, nếu đầu vào là:

const arr = [4, 7, 1, 4, 7, 5, 3, 8, 9];

Thì đầu ra nên là:

const output = [2, 4, 0, 1, 2, 1, 0, 0, 0];

Giải thích đầu ra

Số nhỏ hơn 4 bên phải là 2 (1 và 3), cho 7 là 4 (1, 4, 5, 3), v.v.

Ví dụ minh họa

Mã thực hiện (O(n²) đơn giản):

const arr = [4, 7, 1, 4, 7, 5, 3, 8, 9]; 
const countSmaller = (array = [], num) => array.reduce((acc, val) => { 
  if(val < num){ 
    acc++; 
  }; 
  return acc; 
}, 0); 
const smallerArray = (arr = []) => { 
  const res = []; 
  for(let i = 0; i < arr.length; i++){ 
    const el = arr[i]; 
    res[i] = countSmaller(arr.slice(i, arr.length), el); 
  }; 
  return res; 
}; 
console.log(smallerArray(arr));

Đầu ra

Kết quả trong console sẽ là:

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