精华内容
下载资源
问答
  • 有序矩阵:每行和每列都是递增的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 = 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];
    }
    };
    

    在这里插入图片描述

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

    传送门

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

    输入:
    matrix = [                   k = 8,
       [ 1,  5,  9],
       [10, 11, 13],
       [12, 13, 15]
    ],
    
    输出:                          13
    首先第k大数一定落在[l, r]中,其中l = matrix[0][0], r = matrix[row - 1][col - 1].
    
    我们二分值域[l, r]区间,mid = (l + r) >> 1, 对于mid,我们检查矩阵中有多少元素小于等于mid,记个数为cnt,那么有:
    
    1、如果cnt < k, 那么[l, mid]中包含矩阵元素个数一定< k,
       那么第k小元素一定不在[l, mid]中,必定在[mid + 1, r]中,所以更新l = mid + 1.
    
    2、否则cnt >= k,那么[l, mid]中包含矩阵元素个数就>=k,
       即第k小元素一定在[l,mid]区间中,令r = mid;
    
    至于怎么得矩阵中有多少元素小于等于mid,
    可以利用矩阵本身性质,从右上角开始枚举,具体可参考代码。
    
      	public int kthSmallest(int[][] matrix, int k) {
            int rows = matrix.length, cols = matrix[0].length;
            int start = matrix[0][0], end = matrix[rows - 1][cols - 1];
            while (start < end) {
                int mid = ((end - start) >> 1) + start;
                int count = helper(matrix, mid);
                // 不能在下面返回,mid可能不在矩阵中,让二分自然结束之后返回
                // if (count == k) return mid; 
                if (count < k) start = mid + 1; // count<k 不是 < mid
                else end = mid;
            }
            return start;// count=k时不返回,保证了退出循环时,start一定在矩阵里
        }
        // 统计矩阵中<=mid 的数的个数
        int helper(int[][] matrix, int mid) {
            int count = 0;
            int i = 0, j = matrix[0].length - 1;
            while (i < matrix.length && j >= 0) {
                if (matrix[i][j] > mid) {
                    j--;
                } else {
                   // 这里计算count不要误以为需要加上上面几行的i*matrix.len
                   // 因为i在上一行的时候已经加过了
                   count += (j + 1); 
                   i++;   
                }
            }
            return count;
        }
    

    时间复杂度为O(n*log(m)), n = max(row, col) m代表二分区间的长度,即矩阵最大值和最小值的差

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

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

    -----------------------------------------------------------------------------------------

    解法1:将二维数组中所有元素取出排序

    class Solution(object):
        def kthSmallest(self, matrix, k):
            """
            :type matrix: List[List[int]]
            :type k: int
            :rtype: int
            """
            li = []
            for ma in matrix:
                li.extend(ma)
            li.sort()
    
            return li[k-1]
            

    解法2:类似“二分法”查找的方法

    bisect.bisect_right(row, m)在row中查找m,m存在时返回m右侧的位置,m不存在返回应该插入的位置,这整行代码的意思就是数每一行row中在m值左边的个数并累加。

    class Solution(object):
        def kthSmallest(self, matrix, k):
            """
            :type matrix: List[List[int]]
            :type k: int
            :rtype: int
            """
            l = matrix[0][0]
            r = matrix[-1][-1]
            while (l < r):
                m = l + (r - l) // 2
                total = sum(bisect.bisect_right(row, m) for row in matrix)
                if total >= k:
                    r = m
                else:
                    l = m + 1
            return l    
    

    参考:

    https://blog.csdn.net/weixin_41303016/article/details/88571208

    https://blog.csdn.net/qq_36309480/article/details/90296367

    展开全文
  • 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 元素。 请注意,它是排序后的 k 小元素,而不是 k 个不同的元素。 示例: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15...
  • 给定一个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, 返回 ...
  • 给定一个n x n矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 元素。 请注意,它是排序后的 k 小元素,而不是 k 个不同的元素。 示例: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ...
  • 378.有序矩阵中第K小元素 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小元素。 请注意,它是排序后的第k小元素,而不是第k元素。 实例: 思路: 这个是二维数组,把二维数组转一维...
  • 1、题目描述 数组和矩阵(378):...给定一个n x n矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小元素。 请注意,它是排序后的第k小元素,而不是第k元素。 示例: matrix = [ [ 1, 5...
  • 240. 搜索二维矩阵 II class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix==null||matrix.length==0||matrix[0].length==0) return false; int rows=matrix.length-1; .....
  • 给定一个 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 ...
  • 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], ...
  • LeetCode 有序矩阵中第K小元素

    千次阅读 2019-03-15 19:49:18
    给定一个 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] ], ...
  • 给定一个 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, 返回...
  • 题目:给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 元素。 请注意,它是排序后的 k 小元素,而... * 有序矩阵中第K小元素 * @author LvChaoZhang * */ import java.util.*; p.
  • 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小元素。 请注意,它是排序后的第k小元素,而不是第k元素。 示例: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, 返回 ...
  • 378 有序矩阵中第k小元素 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 元素。请注意,它是排序后的 k 小元素,而不是 k 个不同的元素。 示例 matrix = [ [ 1, 5, 9], [10, ...
  • 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 元素。 请注意,它是排序后的 k 小元素,而不是 k 个不同的元素。 示例: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k ...
  • 378. 有序矩阵中第 K 元素 给你一个 n x n 矩阵 matrix ,其中每行和每列元素均按升序排序,找到矩阵中第 k 元素。 请注意,它是 排序后 的 k 小元素,而不是 k 个 不同 的元素。 输入:matrix = [[1,5,...
  • 使用二分查找的方法,解决《378. 有序矩阵中第K小元素》问题
  • 378、有序矩阵中第K小元素

    千次阅读 2020-07-04 18:08:33
    题目:给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 元素 归并排序 思路及算法   由题目给出的性质可知,这个矩阵的每一行均为一个有序数组。问题即转化为从这 n 个有序数组 k...
  • 378.有序矩阵中第K小元素(中等) 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小元素。 请注意,它是排序后的第k小元素,而不是第k元素。 示例: matrix = [ [ 1, 5, 9], [10, 11, ...
  • 378. 有序矩阵中第K小元素 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 元素。 请注意,它是排序后的 k 小元素,而不是 k 个不同的元素。 示例: matrix = [ [ 1, 5, 9], [10...
  • 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小元素。 请注意,它是排序后的第k小元素,不是第k元素。 而 示例: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,445
精华内容 6,178
关键字:

有序矩阵中第k小元素