是否有 "named" 算法用于按存储桶大小对数组进行分区

Question

我想获取一个输入数组和一组可能的大小，并将该数组划分为子数组，每个子数组的最大可能存储桶大小都小于剩余项数。

所以给定输入数组...

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

还有尺码...

[10, 5, 3, 2, 1]

它会 return 一个像...

这样的数组

[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [11, 12, 13], [14]]

先分区10再分区3再分区1

我可以使用 while 循环等以非常笨拙的方式做到这一点，但我想知道这种算法是否有某种名称，我可以研究一些更优雅的实现方式。

Answer 1

感谢@AnandUndavia，我解决了这个问题，不是作为数组分区练习，而是作为硬币找零问题。

我能够使用此函数解决此问题...（在 Swift 中）

func separate(numberOfItems n: Int, bucketSizes sizes: [Int]) -> [Int] {
    var output = [Int]()
    var remaining = n

    for size in sizes {
        while remaining >= size {
            output.append(size)
            remaining -= size
        }
    }

    return output
}

现在有了我的大小数组，我可以轻松解决我正在处理的其余问题:D

Answer 2

您也可以在单循环中实现。像这样的是 JS:

var inputArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
var sizeArray = [10, 3, 5, 2, 1];
var outputArray = [];

sizeArray.sort(function(a, b) { return b-a}); // Sort array in decreasing order

while(sizeArray.length > 0 && inputArray.length > 0){
  var m = sizeArray[0];
  sizeArray = sizeArray.slice(1); // Pop the first element from Size Array
  if(m <= inputArray.length){
    outputArray.push(inputArray.slice(0, m)); // Extract first m elements from inputArray if its size is greater than m
    inputArray = inputArray.slice(m);
  }
}
console.log(outputArray);

是否有 "named" 算法用于按存储桶大小对数组进行分区

Is there a "named" algorithm for partitioning arrays by bucket sizes

arrays

algorithm

partitioning