如何缩小范围，让他们有大约相同数量的对象

Question

例如，有1000种产品分布不均，价格在100美元到150美元之间。我想让每个价格区间都有相同数量的产品。

我的想法是递归地将其减半，类似于

function cut(min, max, maxNum, result = []){
if (number of min~max > maxNum) {
mid = (max+min)/2
cut(min, mid, maxNum)
cut(mid+1, max, maxNum)
} else {
result.push(`${min}~${max}`)
}
}

它工作得很好，但结果可能包括比乘积的maxNum小得多的范围。

例如，$100~$112只有5个产品，而maxNum=200。

有什么想法或更好的解决方案吗？

Answer 1

我建议按价格对产品进行排序，然后使用Array.slice((.将其划分为N个范围

一旦我们有了范围，我们就可以输出每个范围的计数、最低价格、最高价格等：

const totalCount = 1000;
const maxNum = 200;
const minPrice = 100;
const maxPrice = 150;
// How many ranges to divide into
const rangeCount = totalCount / maxNum;
const rangeSize = totalCount  / rangeCount;
function getRandomPrice() {
return Math.floor(Math.random() * (1 + maxPrice - minPrice)) + minPrice;
}
const products = Array.from({ length: totalCount }, (v, k) => ({ id: k + 1, name: `product ${k + 1}`, price: getRandomPrice()  }));
// Sort our products by price...
const sortedProducts = products.sort(( a, b ) => a.price - b.price);
const ranges = Array.from({ length: rangeCount }, (v, k) => sortedProducts.slice(k * rangeSize, (k + 1) * rangeSize));
console.log('Ranges:');
for(let range of ranges) {
console.log(`Count: ${range.length} Price: $${range[0].price} -> $${range[range.length - 1].price} `)
}

.as-console-wrapper { max-height: 100% !important; }