Что не так с моей реализацией IEquatable <T>, IComparable <T>?SortedList генерирует ArgumentException - PullRequest
Новая
       93

Что не так с моей реализацией IEquatable <T>, IComparable <T>?SortedList генерирует ArgumentException

0 голосов
/ 13 декабря 2018

Я работаю над решением головоломки онлайн и наткнулся на эту проблему, где, учитывая двумерную матрицу и число 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.Но по какой-то причине в вышеприведенном примере объект Point для индекса 1,2 (значение 13) и объект для индекса 2,1 (значение 13) считаются равными, когда они не должны быть.Я получаю ArgumentException при использовании SortedList, а 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;
            }
        }
    }
}


public class Point : IComparable<Point>, IEquatable<Point>
{
    public int x { get; private set; }
    public int y { get; private set; }
    public int val { get; private set; }

    public Point(int x, int y, int val)
    {
        this.x = x;
        this.y = y;
        this.val = val;
    }

    public int CompareTo(Point that)
    {
        if(this.val == that.val) {
            if(this.x == that.x) {
                return this.y.CompareTo(that.y);
            }
            else {
                this.x.CompareTo(that.x);
            }
        }
        return val.CompareTo(that.val);
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != this.GetType()) return false;
        return Equals((Point)obj);
    }

    public bool Equals(Point p1) {
        return x == p1.x && y == p1.y && val == p1.val;
    }

    public override int GetHashCode() {
        long hashCode = ((x * 31 + y) * 31 + val);
        return hashCode.GetHashCode();
    }
}

1 Ответ

0 голосов
/ 13 декабря 2018

В вашем 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);
    }
...