力扣第378题有序矩阵中第K小的元素

题目描述

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例：

matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, 返回 13。

解法1：使用flat()加上sort()之后根据index进行

var kthSmallest = function(matrix, k) { const list = matrix.flat().sort((a,b)=>a-b) return list[k-1] };

解法2：二分查找法

var kthSmallest = function(matrix, k) { let left = matrix[0][0], row = matrix.length, col = matrix[0].length, right = matrix[row - 1][col - 1]; // 判断矩阵中 <= value 的数是不是 >= k //总体思想就是：当前数的下面和右边数都是大于当前当前数 const isValid = (value, k, arr, row, col) => { let count = 0, i = 0, j = col - 1; while (i < row && j >= 0) { //i < row判断是否到了最后一行，j >= 0是否到了数组最前面 if (arr[i][j] <= value) { count += j + 1; //中位数对比每一行的最后一个数，如果比arr[i][col - 1]大，则直接进入下一行对比 i++; } else { j--; //如果中位数比当前行最后一个数小且比上一行大，则在当前行倒序遍历 } } //遍历完后得到count，判断当前弄出的中位数第几小是不是大于指定k return count >= k; } // 二分查找 while (left < right) { let mid = left + ((right - left) >> 1); //第一步 找到中位数 if (isValid(mid, k, matrix, row, col)) { //如果当前k值比当前中位数小，则右侧数减小 right = mid; } else { left = mid + 1;//如果当前k值比当前中位数小，左侧数在中位数的基础上+1 } } return left; };

拓展：

二分查找法：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列