快速O(1)算法将连续数均匀分布到连续的细分中并输出特定的细分边界

Question

我有一个由给定最大数指定的自然数子集。例如，如果给定的是 7 那么列表是

1,2,3,4,5,6,7

现在我得到另一个输入，平均划分列表的细分数。对于任何余数，一个额外的数字被添加到从头开始的每个细分。如果这个数字是3，那么细分的列表就是

[1,2,3][4,5][6,7]

最后第三个输入，给出“细分顺序（在1和细分数之间）”。在上面的例子中如果阶数是1那么输出就是[1,2,3]，如果阶数是2那么输出就是[4,5]

简单的愚蠢方法是先做7/3=2并计算余数7-2*3=1，然后通过先分配1,2生成第一组，然后因为第一组顺序是no余数越大，加一个元素得到1,2,3。然后生成第二组等等

不过在我看来，必须有一种方法可以直接得到一个中间组，而不需要生成所有前面的组。即在给定输入 max_num=7, subdivision_num=3, subdivision_order=3 的情况下得到 [6,7] 而无需通过 for 循环。

现在所需的实际细分输出仅由最小和最大数字表示（即 7,3,1 的输出将是 1,3），因此后者意味着最坏情况 O( 1) 算法，而平凡的愚蠢方式具有最坏情况 O(n) 其中 n 是细分数。

这似乎并不难，但我苦苦挣扎了一段时间却无法提出“直接O(1)”算法。任何帮助将不胜感激。

Answer 1

如果我没有正确理解你的问题，你会得到三个值

最大
段
段索引（基于一个）

并且您想 return 段范围的最小值和最大值。

我们来看一个数字稍大的例子

最大 = 107
段数 = 10
段索引 = 4

好的，算一下

107 (maximum) / 10 (segments) = 10 values in a segment with 7 left over.

因此，前 7 段有 11 个值，后 3 段有 10 个值。其余部分放在第一段。

所以3 * 11 = 33。 3 是从零开始的段索引，前 3 个段有 11 个值，

第 4 段也有 11 个值，所以你会 return 33 + 1 和 33 + 11，或 34 和 44。唯一的“技巧”是确保你用余数和没有余数的段。

您需要计算四个数字。有余数段数、有余数段长度、无余数段数、无余数段长度

在我给出的示例中，将是 7 和 11、3 和 10。然后您添加先前段的计数和想要的段的计数。你用两次乘法来做到这一点。

第一次乘法是余数段的数量乘以余数段的长度。第二次乘法是非余数段的数量乘以非余数段的长度。

同样，使用我给出的例子，那将是

3 * 11 + 0 * 10 = 33

其中 3 是从零开始的段索引，11 是剩余段的长度，0 是非剩余段的数量，10 是非剩余段的长度。

复杂度为 O(1)。

Answer 2

不考虑生成列表的时间，假设分支和算术运算需要常数时间，我们可以在 O(1) 中完成。

parts = max_num // subdivisions_num
rems = max_num % subdivisions_num
if subdivision_order < rems:
  startindex = (parts+1) * (subdivision_order - 1)
  length = parts + 1
  print(numlist[startindex:startindex+length])
else:
  startindex = (parts+1) * rem + parts * (subdivision_order - rem - 1)
  length = parts
  print(numlist[startindex:startindex+length])

我认为您不需要将列表划分为子列表。你可以只计算子数组的开始和长度。

在这种情况下，如果 ~subdivision_order~ 小于 ~max_num~ 和 ~subdivision_num~ 的余数，则只需将 ~subdivision_order - 1~（在索引为 0 的情况下）与 ~max_num // subdivision_num~ 并且长度将为 ~max_num // subdivision_num + 1~ .

Answer 3

这是算法在 JavaScript 片段中的实现。您可以交互式输入参数进行测试。

function partition(size, partitionCount, partitionPosition) {
    if (partitionCount < 1 || partitionCount > size) return null; // Out of range
    if (partitionPosition < 1 || partitionPosition > partitionCount) return null; // Out of range
    // Get the largest partition size
    let partitionSize = Math.ceil(size / partitionCount);
    // Determine how many partitions are that large
    let largerPartitionCount = partitionCount - (partitionSize - size % partitionSize) % partitionSize;
    // Convert 1-based position to 0-based index
    let partitionIndex = partitionPosition - 1;
    // Derive the first and last value of the requested partition
    let first = partitionIndex * partitionSize + 1 - Math.max(0, partitionIndex - largerPartitionCount);
    let last = first + partitionSize - 1 - (partitionIndex >= largerPartitionCount ? 1 : 0);
    return [first, last];
}

// I/O management

let inputs = document.querySelectorAll("input");
let output = document.querySelector("span");

document.addEventListener("change", refresh);

function refresh() {
    let [size, partitionCount, partitionPosition] = Array.from(inputs, input => +input.value);
    let result = partition(size, partitionCount, partitionPosition);
    output.textContent = JSON.stringify(result);
}

refresh();

input { width: 3em }

Array size: <input type="number" value="7" ><br>
Number of partitions: <input type="number" value="3" ><br>
Partition to return: <input type="number" value="1" ><br>
<br>
Returned partition: <span></span>

快速O(1)算法将连续数均匀分布到连续的细分中并输出特定的细分边界

Fast O(1) algorithm to evenly distribute continuous numbers into continuous subdivisions and output a specific subdivision boundary

algorithm

time-complexity