IComparable<T> 实现有什么问题？SortedList 抛出

Question

我正在在线解决一个难题，偶然发现了这个问题，给定一个二维矩阵和一个数字 k，我需要返回矩阵中第 k 个最小的元素。

 matrix = [

       [ 1,  5,  9],

       [10, 11, 13],

       [12, 13, 15]

    ],

    k = 8,

return 13.

我可以通过我自己的二进制堆实现来解决这个问题。由于我正在准备面试，我不确定在所有情况下实现自己的堆是否都是可接受的解决方案。所以我尝试用 SortedList/SortedSet 来解决这个问题。

我基本上是在创建一个 Point 对象，它采用索引 i、j 和 i、j 处的值。我已经实现了 IComparable 和 IEquatable。但是由于某种原因，在上面的示例中，索引 1,2（值 13）的 Point 对象和索引 2,1（值 13）的对象在不应该相等时被视为相等。使用 SortedList 时出现 ArgumentException，同时 SortedSet 只会覆盖现有对象。我对 IEquatable、IComparable 的实现是否错误？我已经仔细检查过它们是否生成了不同的哈希码。

PS这不是作业问题。我正在通过在线面试准备平台解决问题。

public class Solution {

    public int KthSmallest(int[,] matrix, int k) {

        int rows = matrix.GetLength(0);

        int cols = matrix.GetLength(1);

        SortedSet<Point> pq = new SortedSet<Point>();

        bool[,] visited = new bool[rows, cols];

        int count = 1;

        int i=0, j=0;

        var start = new Point(i, j, matrix[i, j]);

        pq.Add(start);

        visited[0, 0] = true;

        while(true) {

            k--;

            var curr = pq.Min;

            pq.Remove(pq.First());

            if(k == 0)

                return curr.val;

            i = curr.x + 1;

            j = curr.y;

            if(i < rows && j < cols && !visited[i, j]) {

                var next = new Point(i, j, matrix[i, j]);

                Console.WriteLine(next.GetHashCode());

                Console.WriteLine(i+", "+j+", "+next.val);

                pq.Add(next);

                visited[i, j] = true;

            }

            i = curr.x;

            j = curr.y + 1;

            if(i < rows && j < cols && !visited[i, j]) {

                var next = new Point(i, j, matrix[i, j]);

                Console.WriteLine(next.GetHashCode());

                Console.WriteLine(i+", "+j+", "+next.val);

                pq.Add(next);

                visited[i, j] = true;

            }

        }

    }

}

Answer 1

您在 CompareTo 中缺少返回语句。我在下面评论了您的原件以及更正的版本。在比较 [2,1] 和 [1,2] 的情况下，x 值不匹配，但是当您点击 this.x.CompareTo 时，您实际上从未返回该比较，因此您的值比较返回。你有：public int CompareTo(Point that)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if(this.val == that.val) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(this.x == that.x) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return this.y.CompareTo(that.y);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //****MISSING RETURN STATEMENT -&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //will return the val.ComapreTo statement after&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //it leaves this block*****&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.x.CompareTo(that.x);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return val.CompareTo(that.val);&nbsp; &nbsp; }你需要：public int CompareTo(Point that)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if(this.val == that.val) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(this.x == that.x) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return this.y.CompareTo(that.y);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return this.x.CompareTo(that.x);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return val.CompareTo(that.val);&nbsp; &nbsp; }