-
Notifications
You must be signed in to change notification settings - Fork 7
/
Program.cs
38 lines (35 loc) · 1.04 KB
/
Program.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using System;
namespace KthSmallestElementInASortedMatrix
{
class Program
{
static void Main(string[] args)
{
int[][] matrix = new int[3][];
matrix[0] = new int[] {1, 5, 9};
matrix[1] = new int[] {10, 11, 13};
matrix[2] = new int[] {12, 13, 15};
int k = 9;
Console.WriteLine(KthSmallest(matrix, k));
}
static int KthSmallest(int[][] matrix, int k)
{
int li = matrix[0][0], hi = matrix[^1][^1] + 1;
while (li < hi)
{
int mid = li + (hi - li) / 2;
int position = 0;
for (int i = 0; i < matrix.Length; i++)
{
int temp = Array.BinarySearch(matrix[i], mid);
position += temp < 0 ? -(temp + 1) : temp;
}
if (position + 1 <= k)
li = mid + 1;
else
hi = mid;
}
return li - 1;
}
}
}