按顺序排列列表

Question

我有一个清单{10,5,3,9,12}.我需要把它转换成像这样的{3,1,0,2,4}.我的意思是将0分配给最小值,将1分配给下一个最小值,依此类推.

我的代码:

     list = {2,3,10,5,1};
     for (int i =list.Count-1; i >= 0 ; i--)
        {

            var maxNo = list.Max();
            var smallIndex = list.IndexOf(maxNo);
            list[smallIndex] = i * -1;

        }
        for (int i = 0; i < list.Count; i++)
        {
            list[i] = list[i] * -1;
        }
        // prints {1,2,4,3,0}

注意:列表仅包含正数.

上面的代码是好的.需要帮助.

Answer 1

基本上你只需要对列表进行排序.看看排序算法.

您可以构造另一个列表,其中包含与从0到列表长度的整数索引配对的原始数字,例如{{10,0}, {5?1}, {3,2}, {9,3}, {12,4}},使用您的编程语言的内置排序函数对此列表进行排序,然后提取整数索引.

编辑:您的程序将工作,但它是相当hackish(使用这些负数),效率非常低.它遍历列表两次,每个元素找到最大值并找到最大值的索引.我建议你阅读有关排序算法的内容.

EDIT2:这个实际的实现可能意味着使用不同的比较函数sort:假设您的原始列表被调用array.让另一个数组idx = {0,1,2,3,4}和排序它不是基于一个比较函数x < y,但array[x] < array[y].

更正

这里的算法找到了所需内容的逆置换.正如唐提到的那样,你需要做另一种反转排列的方法.

Answer 2

您的算法适用于非负整数列表，但正如其他人指出的那样，由于重复的最大值计算，它的效率不高。

我不确定我在这里添加了多少内容，因为 Dan D 的答案是正确的，但也许更多的解释会有所帮助......

{2,3,10,5,1}您在映射示例中寻找的{1,2,4,3,0}是原始列表将在排序列表中占据的索引列表。

最自然的方法是通过排序、索引和“取消排序”，如下所示（并在 Dan D 的更简洁的解决方案中实现）：

向原始数据添加索引列：

{2,3,10,5,1} => {(2,0), (3,1), (10,2), (5,3), (1,4)}

按原始列排序：

{(2,0), (3,1), (10,2), (5,3), (1,4)} => {(1,4), (2,0), (3,1), (5,3), (10,2)}

添加另一个索引列：

{(1,4), (2,0), (3,1), (5,3), (10,2)} => {(1,4,0), (2,0,1), (3,1,2), (5,3,3), (10,2,4)}

通过对第一个索引列进行排序来恢复原始顺序：

{(1,4,0), (2,0,1), (3,1,2), (5,3,3), (10,2,4)} => {(2,0,1), (3,1,2), (10,2,4), (5,3,3), (1,4,0)}

删除原始列和第一个索引列，仅保留中间添加的索引，该索引现在已放入正确的位置：

{(2,0,1), (3,1,2), (10,2,4), (5,3,3), (1,4,0)} => {1,2,4,3,0}

无论原始列表的数据类型是什么，只要它是可以排序的，该策略都将起作用。

由于问题肯定涉及一些排序，因此我强烈怀疑您能否在效率方面做得更好。添加和删​​除列是线性的，排序两次并不比排序一次差多少。