C# version by SortedList


  • 2
    W

    Inspired by selection sort, we use priority queue (SortedList in C#). The special thing here is to deal with duplicates.

    public class Solution {
        public int KthSmallest(int[,] matrix, int k) {
            int r = 0;
            SortedList<int, Tuple<int, int>> s = new SortedList<int, Tuple<int, int>>(new DuplicateKeyComparer<int>());
            for (int i = 0; i < matrix.GetLength(0); i++)
            {
                s.Add(matrix[i, 0], new Tuple<int, int>(i, 0));
            }
            while (k-- > 0)
            {
                r = s.First().Key;
                int x = s.First().Value.Item1, y = s.First().Value.Item2;
                s.RemoveAt(0);
                if (y < matrix.GetLength(0) - 1)
                {
                    s.Add(matrix[x, y + 1], new Tuple<int, int>(x, y + 1));
                }
            }
            return r;
        }
    }
    
    public class DuplicateKeyComparer<TKey> : IComparer<TKey> where TKey : IComparable
    {
        public int Compare(TKey x, TKey y)
        {
            int result = x.CompareTo(y);
            return result == 0 ? 1 : result;
        }
    }

  • 0

    Thank you for your general way of writing a comparer! Very helpful.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.