algorithm - 列表值缩减算法

Question

请原谅，但我很困惑，我找不到任何指向正确方向的资源。

给定 n 个元素的列表:

[3, 6, 5, 1]

将值减少到不大于列表的大小，同时保持相对于彼此的优先级值(按其原始顺序)。

约束:

• 必须维持秩序
• 元素 >= 0
• 不同的值(value)观

我尽量避免排序和创建新列表，而是就地修改列表。

我的预期结果应该是:

[1, 3, 2, 0]

是否存在解决此问题的算法？

Answer 1

您可以在 O(n^2) 中完成此操作。

只需遍历列表n 次，每次将最小元素(while >= i) 设置为i，其中i 从 0 开始递增到 n-1

我怀疑您正在寻找比这更好的东西，但我不确定您可以就地做得更好。

例子:

Input: 3  6  5  1

3  6  5  0*
1* 6  5  0
1  6  2* 0
1  3* 2  0

注意:这假设元素是 >= 0 并且不同