Leetcode: Kth Smallest Element in a Sorted Matrix
LeetCode in Element sorted matrix Smallest
2023-09-11 14:14:07 时间
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 ≤ n2.
Heap: you need to know the row number and column number of that element(so we can create a tuple class here)
1 public class Solution { 2 public int kthSmallest(int[][] matrix, int k) { 3 Comparator<Tuple> comp = new Comparator<Tuple>() { 4 public int compare(Tuple tp1, Tuple tp2) { 5 return tp1.val - tp2.val; 6 } 7 }; 8 9 PriorityQueue<Tuple> minHeap = new PriorityQueue<Tuple>(matrix.length, comp); 10 11 int res = 0; 12 13 for (int row=0; row<matrix.length; row++) { 14 minHeap.offer(new Tuple(row, 0, matrix[row][0])); 15 } 16 17 18 for (int i=1; i<=k; i++) { 19 Tuple tp = minHeap.poll(); 20 if (i == k) { 21 res = tp.val; 22 break; 23 } 24 if (tp.y < matrix.length-1) minHeap.offer(new Tuple(tp.x, tp.y+1, matrix[tp.x][tp.y+1])); 25 } 26 return res; 27 } 28 29 public class Tuple { 30 int x; 31 int y; 32 int val; 33 public Tuple(int i, int j, int value) { 34 this.x = i; 35 this.y = j; 36 this.val = value; 37 } 38 } 39 }
Binary Search方法:(12/28仔细看了之后觉得没必要深究,有时间再去深究吧)
1 public class Solution { 2 public int kthSmallest(int[][] matrix, int k) { 3 int lo = matrix[0][0], hi = matrix[matrix.length - 1][matrix[0].length - 1] + 1;//[lo, hi) 4 while(lo < hi) { 5 int mid = lo + (hi - lo) / 2; 6 int count = 0, j = matrix[0].length - 1; 7 for(int i = 0; i < matrix.length; i++) { 8 while(j >= 0 && matrix[i][j] > mid) j--; 9 count += (j + 1); 10 } 11 if(count < k) lo = mid + 1; 12 else hi = mid; 13 } 14 return lo; 15 } 16 }
referred to https://discuss.leetcode.com/topic/52948/share-my-thoughts-and-clean-java-code/2
相关文章
- Leetcode: Poor Pigs
- Leetcode: Delete Node in a BST
- Leetcode: K-th Smallest in Lexicographical Order
- Leetcode: Maximum XOR of Two Numbers in an Array
- Leetcode: Battleships in a Board
- Leetcode: Kth Smallest Element in a BST
- Leetcode: Basic Calculator
- Leetcode: Populating Next Right Pointers in Each Node
- Leetcode: Find First and Last Position of Element in Sorted Array
- [LeetCode][Java] Populating Next Right Pointers in Each Node II
- [LeetCode] Populating Next Right Pointers in Each Node
- [LeetCode] Generate Parentheses
- [LeetCode]5398. 统计二叉树中好节点的数目
- 【LeetCode】25. Reverse Nodes in k-Group (2 solutions)
- Leetcode Find Minimum in Rotated Sorted Array 题解
- [leetcode]Subsets
- 【leetcode】206: 反转链表
- [LeetCode] 1296. Divide Array in Sets of K Consecutive Numbers 划分数组为连续数字的集合
- [LeetCode] 1041. Robot Bounded In Circle 困于圆圈路径中的机器人
- [LeetCode] 961. N-Repeated Element in Size 2N Array 在大小为2N的数组中重复N次的数字
- [LeetCode] Minesweeper 扫雷游戏
- [LeetCode] Find All Duplicates in an Array 找出数组中所有重复项
- [LeetCode] Unique Substrings in Wraparound String 封装字符串中的独特子字符串
- [LeetCode] Second Highest Salary 第二高薪水
- [LeetCode] 34. Find First and Last Position of Element in Sorted Array 在有序数组中查找元素的第一个和最后一个位置
- LeetCode 3. 无重复字符的最长子串
- leetcode 34. Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位置(中等)