列表值约简算法 [英] List value reduction algorithm
问题描述
原谅我,但我很迷茫,我找不到指向我的方向是正确的任何资源。
Forgive me, but I am very confused and I cannot find any sources that are pointing my in the right direction.
n个元素的给定列表:
Given list of n elements:
[3, 6, 5, 1]
减少值,以不超过该列表的大小,同时保持优先级值相对于彼此(以它们的原始顺序)。
Reduce the values to be no larger than the size of the list while keeping prioritization values relative to one another (In their original order).
约束:
- 订单必须保持
- 元素> = 0
- 在不同的值
我想远离排序并创建一个新的列表,但修改就地列表中。
I am trying to stay away from sorting and creating a new list, but modifying the list in-place.
什么我预期的结果应该是:
What my expected outcome should be:
[1, 3, 2, 0]
有一个算法,存在这个问题?
Is there an algorithm that exists for this problem?
推荐答案
您可以做到这一点为O(n ^ 2)。
You could do this in O(n^2).
刚去通过列表 N
倍,设定的最小元素(虽然> = I
)以我
每一次,其中我
从0开始增量 N-1
Just go through the list n
times, setting the minimum element(while >= i
) to i
each time, where i
starts at 0 and increments to n-1
我怀疑你正在寻找的东西比这更好的,但我不知道有多少你可以更好的就地做。
I suspect you're looking for something better than that, but I'm not sure how much better you can do in-place.
例如:
Input: 3 6 5 1
3 6 5 0*
1* 6 5 0
1 6 2* 0
1 3* 2 0
请注意:这是假定元素> = 0
和鲜明的
Note: this assumes elements are >= 0
and distinct
这篇关于列表值约简算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!