c# - 如何在列表中存储数字对，并且仍然能够根据第一个元素对它们进行排序和二进制搜索？

Question

基本上，我需要能够根据第一个数字进行排序和二分搜索，但我还需要将第二个数字与每个元素相关联。

我不能做键值对，因为键不一定是唯一的。但我觉得这必须足够常见才能保证某种内置解决方案，例如对或其他东西，只是我不知道如何使它们仍然根据对中的第一个整数进行排序。

有什么想法吗？

编辑:

根据你的建议，我用我的脸完成了这个任务:

public class Pair
{
    int first;
    int second;
    public Pair(int x, int y)
    {
        first = x;
        second = y;
    }
    public int CompareTo(Pair compair)
    {
        if (compair != null)
        {
            return this.first.CompareTo(compair.first);
        }
        else
            return 1;
    }
}

我真的希望能有一些内置的东西，如果我需要在某种采访中这样做的话，为了速度，但我想它是有效的。

Answer 1

如上所述，正如您所开始的，您可以创建一个 Pair与您拥有的类进行比较。但这个要求给工作带来了麻烦:

I can't do key value pairs, because the keys aren't necessarily unique.

所以这告诉我你可以有多个具有相同值的 first 对。您可以声明您的Pair类，然后使用 SortedDictionary基于该 key 。它们将在输入时进行排序，您可以执行 O(1) 哈希表查找:

var input = new[]{
    new Pair(1, 1),
    new Pair(5, 2),
    new Pair(1, 2),
    new Pair(2, 1),
    new Pair(7, 4),
    new Pair(3, 1),
    new Pair(7, 2)
};

SortedDictionary<int, List<Pair>> pairs = 
    new SortedDictionary<int, List<Pair>>();

foreach(var pair in input)
{
    if (!pairs.ContainsKey(pair.First))
        pairs.Add(pair.First, new List<Pair>());

    pairs[pair.First].Add(pair);
}

为了完整起见，这里是Pair正如我所声明的那样:

public class Pair : IComparable<Pair>
{
    public int First { get; private set; }
    public int Second { get; private set; }

    public Pair(int first, int second)
    {
        this.First = first;
        this.Second = second;
    }

    public int CompareTo(Pair other)
    {
        if (other != null)
            return this.First.CompareTo(other.First);
        else
            return 1;
    }
}

这可能是我会走的路线(或多或少取决于具体要求)。您还声明:

I was really hoping there'd be something one line and built in

嗯，我能想到的最接近“内置”的是使用 Tuple<int, int>并使用一些 LINQ。为了清楚起见，我将其写成两行，但可以轻松地将其合并为一行:

var input = new[]{
    Tuple.Create(1, 1),
    Tuple.Create(5, 2),
    Tuple.Create(1, 2),
    Tuple.Create(2, 1),
    Tuple.Create(7, 4),
    Tuple.Create(3, 1),
    Tuple.Create(7, 2)
};

var unsortedDictionary = input
    .GroupBy(p => p.Item1)
    .ToDictionary(g => g.Key, g => g.Select(i => i));

var sortedDictionary = 
    new SortedDictionary<int, IEnumerable<Tuple<int, int>>>(unsortedDictionary);

我不确定这是否更好。那里的嵌套元组有点奇怪。如果需要，元组此时会变得多余，因为字典的“键”与每个值都重复，因此您可以将一个“键”与一组“第二”值(每对的后半部分)关联):

var unsortedDictionary = input
    .GroupBy(p => p.Item1)
    .ToDictionary(g => g.Key, g => g.Select(i => i.Item2));

var sortedDictionary = 
    new SortedDictionary<int, IEnumerable<int>>(unsortedDictionary);

至于在工作面试环境中使用以提高速度，您可能必须小心。这里很容易混淆类型(例如，当您只想传递 IEnumerable<int> 时很容易传递 int 并错误声明字典的类型等)