algorithm - 列表值缩减算法

Question

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

给定 n 个元素的列表：

[3, 6, 5, 1]

将这些值减少到不大于列表的大小，同时保持优先级值彼此之间的相对关系（按照它们的原始顺序）。

约束：

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

我试图远离排序和创建新列表，而是就地修改列表。

我的预期结果应该是：

[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不同的

Answer 2

可能有一个，但是如果您考虑解决此问题所需的步骤，则不需要它。

首先，您知道数组中的每个值都不能大于 4，因为这是这个特定示例中的大小。

您需要遍历数组中的每个数字并使用 if 条件检查该数字是否更大；如果是，那么您需要递减它，直到它满足正确的条件（在这种情况下，它小于 4）。

对数组的每个索引执行这些步骤。至于顺序，不要交换任何索引，因为您必须保留原始顺序。希望有帮助！