leetcode----378. 有序矩阵中第K小的元素(javascript的暴力解法与二分解法详解)

Bertha 。 2023-02-22 08:12 17阅读 0赞

#### 一、题目描述 ####

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

#### 二、示例 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70]

#### 三、解题思路 ####

1.  第一种思路是我们可以直接暴力求解，将二维数组展平，再去寻找第K个元素
2.  第二种思路我们可以使用二分法来达到目的：  
    a、确定值的范围是在数组的matrix\[0\]\[0\]到matrix\[n-1\]\[n-1\]之间，  
    b、再去找到中间值，并且算出该数组中比当前值小的个数count  
    c、将count与k比较，如果count比k小的话说明在中间值的右半部分，（要输出这个第k个值），将左边界变成中间值+1，反之亦然。  
    d、如果计算第b步骤中的count呢，我们这样想，因为目前的数组是从左到右，从上到下的升序的，所以我们和每一行的最后一个进行比较，若当前的中间值大于行的最后一列的那个数字时表明该行的数都是小于中间值的数字，count+=该行的个数，row++，比较下一行，如果小于的话，则clumn–来进行判断，最后返回count就是要求的值。

#### 四、代码 ####

//第一种（暴力求解）
    /** * @param {number[][]} matrix * @param {number} k * @return {number} */
    var kthSmallest = function(matrix, k) { 
            var newArr = []
            matrix.forEach(item=>{ 
                newArr = newArr.concat(item)
            })
            newArr.sort((a,b)=>{ return a-b})
            return newArr[k - 1]
    };
    
    //第二种（二分求解）
    /** * @param {number[][]} matrix * @param {number} k * @return {number} */
    const  getCount = (matrix,midd)=>{ 
        let n = matrix.length
        let row = 0;
        let column = n-1
        let count =0
        while(row<n && column>=0){ 
            if(midd>=matrix[row][column]){ 
                count+=column+1
                row++;
            }
            else{ 
                column--;
            }
        }
        return count
    }
    var kthSmallest = function(matrix, k) { 
           const  n = matrix.length
           let low= matrix[0][0]
           let high = matrix[n-1][n-1]
           while(low<=high){ 
               let mid =  low + ((high - low) >>> 1); 
               let count = getCount(matrix,mid)
               if(count<k){ 
                   low = mid+1
               }else{ 
                   high = mid-1
               }
           }
           return low
    };

#### 五、结果 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020070215281454.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200702152628670.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4,size_16,color_FFFFFF,t_70