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)

    {

        if(this.val == that.val) {

            if(this.x == that.x) {

                return this.y.CompareTo(that.y);

            }

            else {

                //****MISSING RETURN STATEMENT - 

                //will return the val.ComapreTo statement after 

                //it leaves this block*****

                this.x.CompareTo(that.x);

            }

        }

        return val.CompareTo(that.val);

    }

你需要：

public int CompareTo(Point that)

    {

        if(this.val == that.val) {

            if(this.x == that.x) {

                return this.y.CompareTo(that.y);

            }

            else {

                return this.x.CompareTo(that.x);

            }

        }

        return val.CompareTo(that.val);

    }