首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode-378.有序矩阵中第K小的元素

Leetcode-378.有序矩阵中第K小的元素

作者头像
程序员小王
发布2019-08-20 10:51:29
1.3K0
发布2019-08-20 10:51:29
举报
文章被收录于专栏:架构说架构说

题目描述

给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。(从升序角度来看,第个k,k越大越靠后)

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

示例:

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

k = 8,

返回 13。
说明: 
你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

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

题目分析

第一步:完成比完美更重要

完成需要解决的2个问题:

1 最简单方式也自己思路,思路依据是什么?能不能正确的执行下去。 算法的第一个要求有有限时间内正确的输出 例如 用折半,用暴力 是不能解决问题的缺乏完整描述

2 试图用巧妙方式,简洁省力方式, 但是用一天时间想不出来方式这样.是错误的方式 简单正确大于错误

Solution 1 : Heap排序

描述:

1. 构建一个m*n大小无序数组heap[m*n],将二维空间变为一维空间 
2. 建堆:进行m*n/2-1 次 堆调整adjust_heap(begin,end)
   对每个非叶子节点从下到上做一次调整
   begin:范围是[m*n/2-1,0]  需要m*n/2-1次

3. 进行k次堆调整,adjust_heap(0,m*n-k)
   heapify是从上至下调整
  每次比它更大元素优先pop,就是大顶堆,排序后是升序
  比它更小最小元素优先pop,就是小顶堆,排序后是降序

 >步骤2和3类比一个tree递归操作,步骤3对root节点进行排序,步骤1是对每个子节点进行排序,每个子节点有是一棵树 

4. heap[0]就是输出结果



Time Complexity: O((k+(m+n)/2log(m*n))= nlogn
space Complexity: O(m*n))
Solution 2 : priority_queue(删除n-k个大的元素)

步骤

1. 建立一个大小为k的优先级队列 
   采用 std:less降序排序,有限输出最大数值,大顶堆
2. 遍历矩阵,

Time Complexity: O(n2)
space Complexity: O(k)
执行用时 :72 ms, 在所有 C++ 提交中击败了44.01% 的用户
内存消耗 :13.2 MB, 在所有 C++ 提交中击败了23.17%的用户

第一步:根据问题来优化(删除k-1小元素)

Solution 3: priority_queue

priority_queue<int,vector,cmp>(cmp为比较函数) priority_queue,采用堆排序实现的,因此排序规则比较特殊:std:greater 是升序(小顶堆),std:less 是降序(采用大顶堆)</int,vector

  1. Build a minHeap of elements from the first row.
  2. Do the following operations k-1 times : Every time when you poll out the root(Top Element in Heap), you need to know the row number and column number of that element(so we can create a tuple class here), replace that root with the next element from the same column.
Solution 4: Binary Search (这个方法很巧妙,但是不常规)

是通过计算来判断的,在理解中

Solution 5: DFS

在理解中

Solution 6: o(n)

最巧妙方法,通过构造区间来实现,在理解中

参考答案

~~~

//函数对象
class Item  
{
public:
int x, y, val;
Item()
{

}
/**
Item (int a, int b, int c):x(a),y(b),val(c)
{   

}
***/
Item (int x, int y, int val) 
{   

this->x = x; //如果成员变量和参数相同,必须用this来区分标记
this->y = y;
this->val = val;

//cout<< "item():"<<this->x<<this->y <<this->val<<endl;

}
/**
    //方法1 重载关系运算符
    bool operator()(const Item  &first,const Item  &second) const{
        return  first.val>second.val;
    }**/
//方法2 重载比较运算符
    bool operator<(const Item& b) const
   {
 return val > b.val;
   }

};

class Solution {
public:

int kthSmallest(vector<vector<int>>& arr, int k) {

int rows = arr.size();
        if ( 0 == rows) return -1;
        int cols = arr[0].size();
priority_queue<Item> min_heap;
   // priority_queue<Item,std::vector<Item>,Item> min_heap;

for (int j=0;j<cols;j++)
        {   
    Item item(0,j,arr[0][j]);
   // cout<< "push" <<item.val<< ":"<<arr[0][j]<<endl;
            min_heap.push(item);
        }
int result=0;
while(k-->0)
{
    Item item = (Item)min_heap.top();
min_heap.pop();
result=item.val;
//cout<< result<<endl;
if (item.x != rows-1)
{  
   Item item1(item.x+1,item.y,arr[item.x+1][item.y]);
   min_heap.push(item1);
}

}
   return result;

}
};
//g++ -g -werror -std=c++11
int main()
{
vector<int> v1 = { 1,  5,  9 };
vector<int> v2 = { 10, 11, 13};
vector<int> v3 = { 12, 13, 15};

vector<vector<int>> board;
board.push_back(v1);
board.push_back(v2);
board.push_back(v3);

Solution solution;
cout<< solution.kthSmallest(board,8);

}
~~~

题型总结

排序算法是最基础的必须掌握的技能,(STL提供了非常丰富排序算法,可以研究) 截至目前理解如下版本1.0: 排序分为2中, 1 全部有序:

sd::stable_sort
稳定排序算法:冒泡排序,插入排序,归并排序 基数排序 

不稳定排序算法:快速排序,希尔排序(shell) ,堆排序 (升序采用大顶堆,降序采用小顶堆)
(每次排序内部不保证是有序的,堆排序每次排序保证第k个元素)

2 部分排序 top k

快速排序和堆排序组成 
std::partial_sort
std::nth_element
唯一的不同在于partial_sort把前 k个元素还进行排列了,而nth_element并不关系他们内部的顺序
nth_element (widgets.begin(),   // 把质量最好的20元素放在
widgets.begin() + 20,     // widgets容器的前面,
widgets.end(),            // 但并不关心这20个元素
qualityCompare);            //本身内部的顺序

下一题目

https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/

欢迎留言讨论

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-08-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Offer多多 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 题目分析
    • Solution 1 : Heap排序
      • Solution 2 : priority_queue(删除n-k个大的元素)
        • Solution 3: priority_queue
          • Solution 4: Binary Search (这个方法很巧妙,但是不常规)
            • Solution 5: DFS
              • Solution 6: o(n)
              • 参考答案
              • 题型总结
              • 下一题目
              相关产品与服务
              容器服务
              腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档