使用 LINQ 排序后获取集合中项的新索引

本文关键字：新索引 索引 排序 LINQ 获取 集合 使用 | 更新日期: 2023-09-27 18:35:57

我想在 C# 中对列表（或数组）进行排序，并希望保存未排序列表中每个项目的新索引。 即：

A = 2 3 1
sorted(A) = 1 2 3
indexes = 1 2 0 <-- This is what I need

我在堆栈溢出上读到LINQ特别有用，但我找不到具体如何做到这一点。

使用 LINQ 排序后获取集合中项的新索引

注意：

我犯了一个可怕的错误，误读了OP的问题（并且很尴尬地收到了这么多赞成票）。我希望（理想情况下）OP接受其他答案之一是正确的。为了公正地对待赞成者，本着SO的精神，我将修改这个答案以使其正确。

可以携带两种扩展方法，一种用于旧索引，另一种用于新索引（这是 OP 想要的）。

public static IEnumerable<int> OldIndicesIfSorted<T>(this IEnumerable<T> source) where T : IComparable<T>
{
    return source
        .Select((item, index) => new { item, index })
        .OrderBy(a => a.item)
        .Select(a => a.index);
}
public static IEnumerable<int> NewIndicesIfSorted<T>(this IEnumerable<T> source) where T : IComparable<T>
{
    return source
        .OldIndicesIfSorted()
        .Select((oldIndex, index) => new { oldIndex, index })
        .OrderBy(a => a.oldIndex)
        .Select(a => a.index);
}

这样称呼它，

//A = [2, 3, 1];
A.NewIndicesIfSorted(); // should print [1, 2, 0]

这两种方法都很懒惰，但理想情况下NewIndicesIfSorted应该根据Matthew Watson的答案编写，这样更有效。我和 Mat 的答案的优点是可以很好地处理重复条目。

您可以使用 LINQ 选择来执行此操作：

var a =new [] {2,3,1};
var sorted = a.OrderBy (x => x).ToList();
var indexes = a.Select (x => sorted.IndexOf(x));

如果这是一个巨大的列表而不是这个简单的列表，它可能有点低效，但确实返回了您所期望的内容。

一种方法如下：

int[] a = {2, 3, 1};
int[] b = Enumerable.Range(0, a.Length).ToArray();
int[] c = new int[a.Length];
Array.Sort(a, b);
for (int i = 0; i < b.Length; ++i)
    c[b[i]] = i;
Console.WriteLine(string.Join(", ", c)); // Prints 1, 2, 0

它使用 Array.Sort() 的重载，该重载使用来自不同数组的值对一个数组进行排序。

我认为这是相当有效的：它使用 O（N log（N）） 排序和 O（N） 重新映射。（其他正确的解是 O（N log（N）） 加上 O（N^2））

但是，它仅适用于数组（因为 List 没有等效的 Array.Sort()）。

使用 Linq 的替代方案（实际上是对@nawfal答案的修正）：

int[] a = {2, 3, 1};
var b = a
    .Select((item, index) => new { item, index })
    .OrderBy(x => x.item)
    .Select(x => x.index)
    .ToArray();
int[] c = new int[b.Length];
for (int i = 0; i < b.Length; ++i)
    c[b[i]] = i;
Console.WriteLine(string.Join(", ", c)); // Prints 1, 2, 0

这里的关键是两种方法中的附加映射步骤：

int[] c = new int[b.Length];
for (int i = 0; i < b.Length; ++i)
    c[b[i]] = i;

这实际上是一个反向查找映射。

另一个工作解决方案：

var input = new List<int> { 2, 3, 1 };
var result = input.Select(x => input.OrderBy(n => n).ToList().IndexOf(x));
Console.WriteLine(String.Join(" ", result));  // 1 2 0

在阅读其他答案时，我对您想要的indexes顺序感到有些困惑，但如果您希望它们按照您在问题中发布的那样按顺序1 2 0，这里有解决方案。试试这个：

var A = new int[] { 2, 3, 1 };
var indexes = new int [A.Length];
var sorted = A.OrderBy(n => n)
              .Select((n, i) => 
                      { 
                          indexes[Array.IndexOf(A, n)] = i;
                          return n; 
                      })
              .ToArray();
相关文章：