代码之家 › 专栏 › 技术社区 › Fogmeister

是否有一个“命名”的算法来按存储桶大小划分数组

partitioning algorithm arrays

Fogmeister · 技术社区 · 8 年前

我想要一个输入数组和一组可能的大小,并将数组划分为子数组,每个子数组都有一个最大可能的bucket大小的计数,该值小于剩余的项数。

所以给定输入数组…

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

尺寸…

[10, 5, 3, 2, 1]

它将返回一个数组,如…

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

首先分区10,然后是3,然后是1。

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

2 回复 | 直到 8 年前

Fogmeister 8 年前

多亏了@anandundavia,我解决这个问题不是作为一个数组分区练习,而是作为一个硬币更换问题。

我能用这个函数解决这个问题…(快速)

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

Ishpreet 8 年前

您也可以在单循环中实现这一点。像这样的是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);

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

1 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

1 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

1 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

1 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

1 年前