问题描述

给定一个矩阵，矩阵的各行和各列都是递增的，找出第k大的元素。
例如：
1,2,8,9
2,4,9,12
4,7,10,13
6,8,11,15

Code

#include <iostream>
using namespace std;
#define INT_MAX 65535
#include <vector>

int findKthValue(vector<vector<int> > & a , int rows ,int cols, int k ){
    int i ,j;
    int min = a[0][0];
    int minOfRows[rows];

    for(i = 0; i < rows; i++)
        minOfRows[i] = 0;

    //记录寻找过程中，各行最小值的所在列
    minOfRows[0] = 1;

    int r;
    //找k个数
    for(i = 1; i < k; i++)
    {
        min = INT_MAX;
        //找到最小值所在的行，每次执行都能找到一个最小值，并且记录最小值所在行
        for(j = 0; j < rows; j++)
        {
            if (minOfRows[j] < cols)
            {
                if(a[j][minOfRows[j]] < min)
                {
                    min = a[j][minOfRows[j]];
                    r = j;
                }
            }
        }
        minOfRows[r]++;  //最小值在该行，下次访问时从下一值开始
    }
    return min;
}
int main()
{
    int rows = 4;
    int cols = 4;
    vector<vector<int>> a = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};//按行初始化

    int k = 10;
    int kth = findKthValue( a , rows, cols,k);

    cout<<kth<<endl;
}

心得

剑指offer上有个类似的题，03题，是在行列有序的矩阵中，查找是否存在某个数。
虽然背景相似，但是问题却是不同的问题。