精华内容
下载资源
问答
  • 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。 请注意,它是排序后的第k小元素,而不是第k个元素。 示例: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, ...

    题目描述

    
    给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。
    请注意,它是排序后的第k小元素,而不是第k个元素。
    
    示例:
    
    matrix = [
       [ 1,  5,  9],
       [10, 11, 13],
       [12, 13, 15]
    ],
    k = 8,
    
    返回 13。
    说明:
    你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。
    

    简单分析

    想到最小堆,试了一下过了,但是因为我最小堆好像只能一维数组,这个转换为一维又空间占用很多的样子emmmm有序二维数组这个特点应该可以利用一下

    代码

    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) {
        vector<int> nums;
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix.size();j++){
                nums.push_back(matrix[i][j]);
            }
        }
        make_heap(nums.begin(),nums.end(),greater<int>());
        while(k>1){
            pop_heap(nums.begin(),nums.end(),greater<int>());
            nums.pop_back();
            k--;
        }
        return nums[0];
    }
    };
    

    在这里插入图片描述

    展开全文
  • 有序矩阵:每行和每列都是递增的Output:矩阵元素从小到大排序后第k元素Example:matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, return 13.思路:二分查找1.以值空间为搜索空间2.以统计个数与k...

    有序矩阵:每行和每列都是递增的

    Output:矩阵元素从小到大排序后第k个元素

    Example:

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

    思路:

    二分查找

    1.以值空间为搜索空间

    2.以统计个数与k比较作二分区间判断

    代码实现:

    func kthSmallest(matrix [][]int, k int) int {
    	n := len(matrix)
    	low := matrix[0][0]
    	high := matrix[n-1][len(matrix[0])-1] + 1
    	for low < high {
    		mid := low+ (high-low) / 2
    		count := 0
    		j := len(matrix[0]) - 1
    		for i := 0; i < n; i++ {
    			for j >= 0 && matrix[i][j] > mid {
    				j--
    			}
    			count += j + 1
    		}
    		if count < k {
    			low = mid + 1
    		} else {
    			high = mid
    		}
    	}
    	return low
    }

    展开全文
  • 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。 请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。 示例: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k ...

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

    示例:

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

    返回 13。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    二分法:

    class Solution {
        public int kthSmallest(int[][] matrix, int k) {
            int n = matrix.length;
            int left = matrix[0][0];
            int right = matrix[n-1][n-1];
            while(left < right){
               int mid =  left + ((right - left)>>1);//这里用这种方式是为了防止溢出,并且能加快速度
               //>>1相当于/2
                if(test(matrix,mid,k,n)){
                    right = mid;
                }else{
                    left = mid + 1;
                }
            }
            return left;
        }
    
        public boolean test(int[][] matrix,int mid,int k,int n){
            int i = n-1;
            int j = 0;
            int num = 0;//保存比mid小的数的个数
            while(i >= 0 && j < n){
                if(matrix[i][j] <= mid){//左边的数都比mid小
                    num += i+1;
                    j++;
                }else {i--;}//否则找上面一个数
            }
        return num >= k;
        }
    }
    
    展开全文
  • 题目链接:有序矩阵中第K小的元素 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。 请注意,它是排序后的第 k 小元素,而不是第 k 个元素。 输入描述 第一行为 k 的值和矩阵的 n ...

    题目

    题目链接:有序矩阵中第K小的元素

    给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。

    请注意,它是排序后的第 k 小元素,而不是第 k 个元素。

    输入描述

    第一行为 k 的值和矩阵的 n 的值
    后续为 n * n 矩阵的数字,以空格分割

    输出描述

    矩阵中第k小的元素

    样例输入

    8 3
    1 5 9
    10 11 13
    12 13 15

    样例输出

    13

    代码

    import java.util.Scanner;
    
    /**
     * 思路:
     *      如果直接用排序的话,时间复杂度为 O(2*n*n*logn)
     *
     *      因为这个二维数组每一行每一列都是有序的,所以可以通过二分来进行优化
     */
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int k = scanner.nextInt(), n = scanner.nextInt();
            int data[][] = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    data[i][j] = scanner.nextInt();
                }
            }
            System.out.println(findKthNum(data, k));
        }
    
        // 二分套二分,时间复杂度 O(n*logn*logn)
        public static int findKthNum(int[][] matrix, int k) {
            int row = matrix.length;
            int col = matrix[0].length;
            int low = matrix[0][0];
            int high = matrix[row - 1][col - 1];
            while (low <= high) {
                int count = 0;
                int mid = low + ((high - low) >> 1);
                for (int[] item : matrix) {
                    count += binarySearchCount(item, mid);
                }
                if (count < k) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            // 返回的 low 表示满足 count >= k 的最小的数,这个数就是要找的第k个数
            return low;
        }
    
        // 返回数组 data 中个小于等于 k 的数的个数
        public static int binarySearchCount(int[] data, int k) {
            int begin = 0, end = data.length - 1;
            while (begin <= end) {
                int mid = (begin + end) >> 1;
                if (data[mid] <= k) {
                    begin = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            return begin;
        }
    }

    转载于:https://www.cnblogs.com/debugxw/p/11479638.html

    展开全文
  • 一、有序矩阵中第K小元素是什么? 二、具体实现 前言 运用Scala中的语法实现有序矩阵中第K小元素 一、有序矩阵中第K小元素是什么? 给定一个n x n矩阵,其中每行和每列元素均按升序排序,找到矩阵...
  • Java实现 LeetCode 378 有序矩阵中第K小元素

    万次阅读 多人点赞 2020-03-11 16:46:24
    378. 有序矩阵中第K小的元素 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。 请注意,它是排序后的第k小元素,而不是第k个元素。 示例: matrix = [ [ 1, 5, 9], [10, 11, 13], ...
  • 378. 有序矩阵中第K小的元素 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。 请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。 思路 考虑到是在有序矩阵中寻找第K...
  • 378. 有序矩阵中第K小的元素 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。 请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。 示例: matrix = [ [ 1, 5, 9], [10...
  • 378.有序矩阵中第K小的元素 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。 请注意,它是排序后的第k小元素,而不是第k个元素。 实例: 思路: 这个是二维数组,把二维数组转一维...
  • 378. 有序矩阵中第K小元素题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix题目给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的...
  • 这道题让我们求有序矩阵中第K小元素,这道题的难点在于数组并不是蛇形有序的,意思是当前行的最后一个元素并不一定会小于下一行的首元素,所以我们并不能直接定位第K小的元素,所以只能另辟蹊径。先来看一种利用堆...
  • 378. 有序矩阵中第K小的元素题目给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。示例:matrix = [[ 1, 5, 9],[10, 11...
  • 有序矩阵中第K小的元素 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。 请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。 示例: matrix = [ [ 1, 5, 9], ...
  • LeetCode 378:有序矩阵中第k小的元素题目描述解题思路代码实现总结 题目描述 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。 请注意,它是排序后的第k小元素,而不是第k个元素。 ...
  • 378.有序矩阵中第K小的元素(中等) 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。 请注意,它是排序后的第k小元素,而不是第k个元素。 示例: matrix = [ [ 1, 5, 9], [10, 11, ...
  • 有序矩阵中第K小的元素 题目详情 题目链接 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。 请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。 示例: matrix = [ ...
  • 378. 有序矩阵中第K小的元素 给定一个n x n矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。 请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。 示例: matrix = [ [ 1, 5, 9], ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 477
精华内容 190
关键字:

有序矩阵中第k小元素