在c#中搜索多维数组

Question

有一个多维数组

int[,] PDATVL = new int[100,2];

设虚拟数据为:

249 398
249 423
249 448
249 473
249 498
251 17
251 42
251 325
252 142
252 418
253 194
254 7
254 319
255 81
255 378

现在我想在数组中搜索251,142对。除了线性搜索，最好的方法是什么呢?

Answer 1

给定数组按词法顺序排序，您有两个选项:

1. 编写一个自定义的二进制搜索方法，用于二维数组
2. 编写一个存储一对整数的结构体，并实现IComparable<T>和IEquatable<T>

我会选择选项二。这种结构的基本实现是:

public struct Pair : IComparable<Pair>, IEquatable<Pair>
{
    private readonly int x;
    private readonly int y;
    public Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
    public int X { get { return x; } }
    public int Y { get { return y; } }
    public int CompareTo(Pair other)
    {
        return (x == other.x) ? y.CompareTo(other.y) : x.CompareTo(other.x);
    }
    public bool Equals(Pair other)
    {
        return x == other.x && y == other.y;
    }
}

现在你可以使用Array.BinarySearch方法:

var pairs = new[] {new Pair(1, 1), new Pair(1,2), new Pair(1, 3), new Pair(2, 3), new Pair(2, 4)};
// Returns 2
int index1 = Array.BinarySearch(pairs, new Pair(1,3));
// No match. Returns a negative number.
int index2 = Array.BinarySearch(pairs, new Pair(1, 4));

Answer 2

如果使用的是对，为什么不使用

HashSet<KeyValuePair<int, int>>  

或

List<KeyValuePair<int, int>>

如果不在。net 4.

然后你可以像这样搜索一对:

pairs.Where(p=> p.Key == 251 && p.Value == 142); 

Answer 3

如果数组已排序，则可以使用二进制搜索。

内置方法Array.BinarySearch只处理一维数组，所以您必须自己实现它。

Answer 4

如果对中每个值都有最大值，则可以将它们组合为单个值，如下所示:

long pair = value1 * 10000000 + value2; // assuming value2 < 1000000

，然后将它们存储在Dictionary(或。net 4中的HashSet)中，这样搜索是O(1):

var d = new Dictionary<long, object>;
long pair1 = 251 * 1000000 + 142;
d.Add(pair1, null);
long pair 2 = ....
// ...
var exists = d.ContainsKey(pair1);