修改選擇算法來選擇加權項

Question

我試圖修改選擇算法有以下情況的工作：

我的開關輸入是數字X1，X2，...，Xn中的列表（不一定訂購） 。

這些數字中的每一個都具有權重「w」。我稱W是所有權重的總和。

如果我提供一個大於0但不大於W的​​值X，我該如何找到xi，使得索引大於i的所有x的權重之和小於X，並且xi的權重+索引大於i的所有項的權重之和大於或等於X.

如果我們根據索引對所有x進行排序，這很容易實現，但是我希望在沒有排序的情況下執行此操作。

Answer 1

如果給出標識符i，則不應該對它們進行排序。這聽起來像你想要它們的標識符的順序，這是已知的，所以你只需要通過列表O（n）來使它們按順序排列。然後按照發布的解決方案之一找出i的適當值。我誤解了這個問題嗎？

更新

因此，可以說你有四個值，該標識符是這樣的：

[ x4, x1, x3, x2 ] 

及其權重分別是：

[ 14, 10, 5, 19 ] 

所有你需要做的首先按順序獲取列表。它與排序不同，因爲在這個原因中，你有x1 .. xn，其中的數字都是連續的，沒有重複等。所以你知道結果將是一個新的大小爲4的列表。

Make one通過第一個列表。在這種情況下，第一個數字的標識符爲4，因此將其放置在位置4的新列表中，並將第一個權重放置在位置4的新權重列表中。接下來將置於位置1，如此等等第四。

這一次通過後，您的名單看起來像：

[ x1, x2, x3, x4 ] and [ 10, 19, 5, 14] 

所以你現在有你想要的順序。在這一點上變得很容易，只需從權重列表的末尾開始，最多再遍歷一次列表即可找到要查找的屬性。

因此它應該是O（n）。