lintcode401. 排序矩阵中的从小到大第k个数

桃扇骨 2023-07-08 02:37 2阅读 0赞

在一个排序矩阵中找从小到大的第 k 个整数。排序矩阵的定义为：每一行递增，每一列也递增。

样例
    样例 1:
    
    输入:
    [
      [1 ,5 ,7],
      [3 ,7 ,8],
      [4 ,8 ,9],
    ]
    k = 4
    输出: 5
    样例 2:
    
    输入: 
    [
      [1, 2],
      [3, 4]
    ]
    k = 3
    输出: 3
    挑战
    时间复杂度 O(klogn), n 是矩阵的宽度和高度的最大值

一个错误的思路：从第一个数开始放入优先队列，map记录该数所对应的矩阵坐标，然后比第二小的数必然与第一小的数相邻，即要么是【x+1】【y】，要么就是【y+1】【x】，如此bfs，找到第k个数即可，但是一旦遇到相同的相邻的数相同，map就无法同时记录两个数，导致错误

class Solution {
        
    public:
        /**
         * @param matrix: a matrix of integers
         * @param k: An integer
         * @return: the kth smallest number in the matrix
         */
        
        int kthSmallest(vector<vector<int>> &matrix, int k) {
        
            // write your code here
            if(matrix.size()<=0||k<=0) return 0;
            priority_queue<int,vector<int>,greater<int>>q;
            map<int,pair<int,int>> tmp;
            int rlen=matrix.size();
            int clen=matrix[0].size();
            int res=0;
            int cnt=0;
            q.push(matrix[0][0]);
            tmp[matrix[0][0]]=make_pair(0,0);
            while(cnt<k&&!q.empty())
            {
        
                cnt++;
                if(cnt==k) return q.top();
                int num=q.top();
                q.pop();
                int x=tmp[num].first;
                int y=tmp[num].second;
                if(x+1<rlen)
                {
        
                    q.push(matrix[x+1][y]);
                    tmp[matrix[x+1][y]]=make_pair(x+1,y);
                }
                if(y+1<clen)
                {
        
                    q.push(matrix[x][y+1]);
                    tmp[matrix[x][y+1]]=make_pair(x,y+1);
                }
            }
            return 0;
        }
    };

正确思路：用一个结构保存坐标和值，重载操作符，使得优先队列按照值的从小到大排序  
注意点不能重复压入队列

class Solution {
        
    public:
        /**
         * @param matrix: a matrix of integers
         * @param k: An integer
         * @return: the kth smallest number in the matrix
         */
    	struct point {
        
    		point(int x, int y,int value) :x(x), y(y),value(value) {
        }
    		friend bool operator<(point point1, point point2)
    	    {
        //重写priority_queue的排序方式，有小到大排序
    			return point1.value > point2.value;
        	}
    		int x;
    		int y;
    		int value;
    	};
        int kthSmallest(vector<vector<int>> &matrix, int k) {
        
            // write your code here
            if (matrix.size() <= 0 || k <= 0) return 0;
    		int rlen = matrix.size();
    		int clen = matrix[0].size();
    		priority_queue<point> q;
    	    vector <vector<bool>> judge(rlen,vector<bool>(clen,false));
    	    //判断该点是否已经加入过队列
    		point tmp(0, 0,matrix[0][0]);
    		q.push(tmp);
    		judge[0][0];
    		int cnt = 0;
    		while (cnt!=k)
    		{
        
    			cnt++;
    			if (cnt == k) return q.top().value;
    			int x = q.top().x;
    			int y = q.top().y;
    			q.pop();
    	       if (x + 1 < rlen)//注意越界
    		    {
        
    		    	point tmp(x + 1, y, matrix[x + 1][y]);
    		    	if (!judge[x+1][y])
    		    	{
        
    		    		q.push(tmp);
    		    		judge[x + 1][y] = true;
    		    	}
    		    }
    	    	if (y + 1 < clen) {
        
    	    		point tmp(x, y + 1, matrix[x][y + 1]);
    	    		if (!judge[x][y+1])
    	    		{
        
    	    			q.push(tmp);
    	    			judge[x][y + 1] = true;
    	    		}
    	    	}
    		}
    		return 0;
        }
    };