给定一个 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 试图用巧妙方式,简洁省力方式, 但是用一天时间想不出来方式这样.是错误的方式 简单正确大于错误
描述:
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))
步骤
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小元素)
priority_queue<int,vector,cmp>(cmp为比较函数) priority_queue,采用堆排序实现的,因此排序规则比较特殊:std:greater 是升序(小顶堆),std:less 是降序(采用大顶堆)</int,vector
是通过计算来判断的,在理解中
在理解中
最巧妙方法,通过构造区间来实现,在理解中
~~~
//函数对象
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/
欢迎留言讨论