我有一個由給定最大數指定的自然數子集。例如，如果給定的是 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，然后由于第一組順序沒有余數，添加一個元素 get 1,2,3。然后生成第二組等等。
但是在我看來，必須有一種方法可以直接獲得中間組，而無需生成所有前一組。即[6,7]在max_num=7, subdivision_num=3, subdivision_order=3不經過 for 回圈的情況下獲得輸入。
現在所需要的實際細分輸出僅由最小和最大數字表示（即，輸出7,3,1將是1,3），因此后者將意味著最壞情況O（1）演算法而瑣碎啞方式具有最壞的情況下為O（n）哪里n是細分編號。
這似乎并不難，但我有一段時間無法提出“直接 O(1)”演算法。任何幫助，將不勝感激。
uj5u.com熱心網友回復：
不考慮生成串列的時間，假設分支和算術運算需要常數時間，我們可以在 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~。
uj5u.com熱心網友回復：
如果我正確理解你的問題，你會得到三個值
- 最大限度
- 段
- 段索引（基于一個）
并且您想回傳段范圍的最小值和最大值。
讓我們看一個數字稍大的例子
- 最大值 = 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 個值，因此您將回傳 33 1 和 33 11，或 34 和 44。唯一的“技巧”是確保區分有余數的段和沒有余數的段。
您需要計算四個數字。有余數的段數、有余數的段長、無余數的段數、無余數的段長。
在我給出的示例中，這將是 7 & 11、3 & 10。然后您將先前段的計數和所需段的計數相加。你用兩個乘法來做到這一點。
第一個乘法是余數段的數量乘以余數段的長度。第二個乘法是非剩余線段的數量乘以非剩余線段的長度。
再一次，使用我給出的例子，那就是
3 * 11 0 * 10 = 33
其中 3 是從零開始的段索引，11 是余數段的長度，0 是非余數段的數量，10 是非余數段的長度。
復雜度為 O(1)。
uj5u.com熱心網友回復：
這是該演算法在 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>轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/391640.html
上一篇：使用拆分合并方法就地反轉陣列