列表值约简算法 [英] 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 倍，设定的最小元素（虽然＆GT; = 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

请注意：这是假定元素＆GT; = 0 和鲜明的

Note: this assumes elements are >= 0 and distinct

这篇关于列表值约简算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！