---
tags: LeetCode
---

# 378. Kth Smallest Element in a Sorted Matrix
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
return 13.

Note:
`You may assume k is always valid, 1 ≤ k ≤ n^2.`

輸入範本如下

public class Solution {
    public int KthSmallest(int[][] matrix, int k) {
    }
}

### 直覺想法
1. 把東西塞進 List , 排序 , 排序後取第 k 個.

    148 ms	32.3 MB
    You are here!
    Your runtime beats 44.53 % of csharp submissions.
    public int KthSmallest(int[][] matrix, int k)
    {
        List<int> list = new List<int>();
        for(int i=0;i< matrix.GetLength(0);i++){
            foreach (var item in matrix[i])
            {
                list.Add(item);
            }
        }
        list.Sort();
        return list[k - 1];
    }

2. 借鏡 [88. Merge Sorted Array](https://hackmd.io/8muWdCrGRwyFHFAf6hceew?view) 的方式排序

    160 ms	31.3 MB
    You are here!
    Your runtime beats 39.42 % of csharp submissions.
    public int KthSmallest(int[][] matrix, int k)
    {
         int dim = matrix.GetLength(0);
         int[] arr = new int[dim * dim];

         for (int i = 0; i < dim; i++)
         {
              Merge(arr, dim * i, matrix[i], dim);
         }
         return arr[k - 1];

         void Merge(int[] nums1, int m, int[] nums2, int n)
         {
              int totalIndex = m + n - 1, n1Index = m - 1, n2Index = n - 1;
              // 由最右邊開始比較 , 較大的先排入 num1[totalIndex] 
              while (n1Index >= 0 && n2Index >= 0)
              {
                   nums1[totalIndex--] = nums1[n1Index] >= nums2[n2Index] ? nums1[n1Index--] : nums2[n2Index--];
              }
              while (n1Index >= 0)
              {
                   nums1[totalIndex--] = nums1[n1Index--];
              }
              while (n2Index >= 0) // num1 已經排完了 , 但 num2 還沒
              {
                   nums1[totalIndex--] = nums2[n2Index--];
              }
         }
    }

3. 二分搜尋法

    120 ms	31.1 MB
    You are here!
    Your runtime beats 86.67 % of csharp submissions.
    public int KthSmallest(int[][] matrix, int k)
    {
        int n = matrix.GetLength(0) - 1;
        int left = matrix[0][0], right = matrix[n][n];
        while (left < right)
        {
            int mid = left + (right - left) / 2, count = 0;

            for (int row = 0; row <= n; row++)
            {
                int column;
                for (column = n; column >= 0 && matrix[row][column] > mid; column--) ;
                count += column + 1;
            }
            if (count < k)
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
        }
        return left;
    }

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: