A. 问题描述
 
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 
B. 问题分析
 
其实笨方法有很多种啦： 
 * 全部无脑遍历一次，时间复杂度为O(NM） 
 * 对每行/列做二分查找，时间复杂度为O(Nlog M） 
 * 好像还不够好，可以整体用二分吗？
 
我们来看一个性质，对于一个N*M的如题所述的矩阵A，如果存在某个值等于要找的target值，看A的最右上角的元素key = A[0][M-1]，从这个位置每步向左走或向下走，必定存在一条路径到达target。
 
所以关键是如何走出这样一条路径出来？
 
其实需要先对矩阵的性质有一个了解。如下图所示，注意区域2只有一个元素，就是当前矩阵的右上角的位置，很明显，区域1的所有值都是不大于key（即区域2的值），而区域4的所有值都是不小于key的，区域3的元素的值与key暂时没有明确的关系。
 
不过上面的性质已经足够加快很多了！！！ 
 1. 如果target = key，那么就找到咯！ 
 2. 比如发现target > key，那么明显区域1和2都没必要继续搜索了，对不对？现在需要搜索的矩阵变成了区域3和区域4组成的新的子矩阵了！！！ 
 3. 反之，如果target < key，那么也很明显，区域2和区域4就没必要搜索了，接下来只需要搜索区域1和区域3组成的子矩阵即可！
 
所以，总的来说，这个算法的复杂度为O(N + M)，应该能够很容易分析出来吧？ 
 
 
C. 代码实现
 
class Solution {
public:
    bool Find(vector<vector<int> >& array, int target) {
        if (array.empty())
            return false;
        int rowSize = array.size(), colSize = array[0].size();
        int x = 0, y = colSize - 1;
        while (check(0, rowSize, x) && check(0, colSize, y)) {
            if (target == array[x][y])
                return true;
            else if (target < array[x][y])
                --y;
            else
                ++x;
        }

        return false;
    }

    bool check(int lower, int upper, int now) {
        return now >= lower && now < upper;
    }
};
 
D. 还有更快的算法吗？
 
应该是有的，不过有点复杂，思路是——在对角线上做二分查找，然后递归下去，这样的话，分治收敛得更快，有兴趣的可以实现出来交流一下，我等下次回来再实现。【未完待续】
 
 
参考：July的《编程之法》4.2节

 
文章目录
 
378. 有序矩阵中第K小的元素
题目
解题思路
代码实现
实现结果
  
 

 
378. 有序矩阵中第K小的元素
 
 
题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
 
题目
 
 
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
 
示例：
 
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13。
 
提示：
 
你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。
 
解题思路
 
 
先审题，题目中给出的是二维数组，而问题需要求得的是二维数组中第 k 小的元素。在这里，最直接的方法就是将二维数组转换为一维数组，对于转换后的一维数组进行升序排序，那么此时的一维数组中的第 k 个元素就是所求的结果。代码大致如下：
 
# python
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
    res = []
    for row in matrix:
        for ele in row:
            res.append(ele)
    res.sort()
    return res[k-1]
 
在这里，代码并没有使用矩阵的特性。而是转换为一维数组进行求解。这个解法的时间复杂度为 O(n^2logn)，即是对 n x n 个数进行排序。
 
因为上面的解法是将矩阵转换为一维数组，并不是在矩阵的基础上解决问题。下面使用二分查找，来尝试以在矩阵的前提下，对问题进行分析解答。
 
思路：二分查找
 
考虑使用二分查找的原因，因为题目中说明，矩阵中，每行每列元素都是升序排序的。
 
也就是说在题目给定的矩阵当中，元素由左上到右下是递增的，以示例为基础扩充展开分析：
 
示例：
 
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8
 
将上面的示例稍微扩充如下（仅为更方便展示二分查找方法的效果）：
 
matrix = [
   [ 1,  5,  9, 10, 11],
   [10, 11, 13, 14, 15],
   [12, 13, 15, 16, 17],
   [13, 14, 16, 17, 18],
   [14, 18, 22, 26, 30]
],
k = 8
 
将上面二维数组转换为下图：
 
 
我们假设左上角的元素为 matrix[0][0]，右下角的元素为 matrix[n-1][n-1]，根据题意以及上面的示图可知。matrix[0][0] 是二维数组中的最小值，matrix[n-1][n-1] 是最大值。
 
我们现在使用二分查找的方法来分析，设 matrix[0][0] 和 matrix[n-1][n-1] 分别为 left 和 right。
 
现在我们尝试取 mid（left <= mid <= right），可以发现在矩阵当中小于等于 mid 值的元素会分布在矩阵的左上部分，而大于 mid 值的元素则分布在矩阵的右下部分。例如下图所示，此时取 mid 为 15：
 
 
在这里大于 mid 和小于等于 mid 的元素分为两部分，沿着红色的分割线将两者分开。此时，我们就可以看到，大于 mid 和小于等于 mid 两者元素的个数分别有多少。
 
上面红色分割线划分的依据，在这里进行分析：
 
因为每行每列的元素都是升序排列的，我们前面的分析，元素需要与 mid 进行比较。例如，我们现在要求分布在左边部分的元素，也就是元素值小于等于 mid 的部分。
 
此时我们可以考虑从左下角开始出发，往右上角去找。这样能够快速收缩范围。具体的流程如下：
 
以左下角为起始点，往右上角开始扩散
如果当前位置的元素值小于等于 mid 值时，说明从当前位置开始往上的所有元素都小于等于 mid（因为每列升序排列），记录当前元素个数 count，注意维护更新。
此时满足元素值小于等于 mid 值时，向右边移动再次比较。否则，就向上移动，寻找稍小的元素进行比较，直至移动到边界。
 
在这里，当取 mid 值后进行划分时，按照上面的方法，能够确定小于或等于 k 的个数，那么就会出现以下两种情况：
 
当 count 大于或等于 k 时，那么可以确定要找的答案在 [left, mid] 这边；
否则，答案在 [mid+1, right] 这个区间。
 
那么根据这个思路，循环直至找到答案。
 
关于二分查找方法执行流程，可看如下简略图示（若不太理解，可手画图帮忙理解）：
 
 
具体的代码实现如下。
 
代码实现
 
 
class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        def search(mid, n):
            # 从左下角开始往右上角找
            i, j = n-1, 0
            # 统计小于或等于 mid 的元素个数
            count = 0
            while i >= 0 and j < n:
                if matrix[i][j] <= mid:
                    # 当此时元素小于等于 mid
                    # 那么该元素往上的所有元素都会小于或等于 mid
                    count += (i + 1)
                    # 向右移动，继续比较
                    j += 1
                else:
                    # 当此时元素大于 mid 时，说明这个元素不包含在内，往上移动
                    i -= 1
            # count 与 k 值比对，判断所求元素落在哪边
            return count >= k
        
        n = len(matrix)

        left, right = matrix[0][0], matrix[n-1][n-1]

        while left < right:
            mid = left + (right - left) // 2
            if search(mid, n):
                # 当 count 大于等于 k 时，表明答案落在 [left, mid]
                # 否则落在 [mid+1, right]
                right = mid
            else:
                left = mid + 1
        
        return left
 
实现结果
 
 
 
 
 
 
文章原创，觉得写得还可以，欢迎关注点赞。微信公众号《书所集录》同步更新，同样欢迎关注。
 
 

题目：给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素
 
归并排序
 
思路及算法
 
  由题目给出的性质可知，这个矩阵的每一行均为一个有序数组。问题即转化为从这 n 个有序数组中找第 k 大的数，可以想到利用归并排序的做法，归并到第 k 个数即可停止。
 
一般归并排序是两个数组归并，而本题是 n 个数组归并，所以需要用小根堆维护，以优化时间复杂度。
 
public int kthSmallest2(int[][] matrix, int k){

        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            pq.offer(new int[]{matrix[i][0], i, 0});
        }
        //维护最左侧的一列最小值候选人，当有序队列弹出7个最小值，此时队列中的最小值即为所求
        for (int i = 0; i < k - 1; i++) {
            int[] now = pq.poll();
            if (now[2] != n - 1) {
                pq.offer(new int[]{matrix[now[1]][now[2] + 1], now[1], now[2] + 1});
            }
        }
        return pq.poll()[0];
    }
 
时间复杂度：O(klogn)，归并 k 次，每次堆中插入和弹出的操作时间复杂度均为logn。
 空间复杂度：O(n)，堆的大小始终为 n。
 
其实解决这个问题的关键，在于维护一组“最小值候选人”
 在整个矩阵中，每次弹出矩阵中最小的值，第k个被弹出的就是我们需要的数字。
 
现在我们的目的很明确：每次弹出矩阵中最小的值。你需要保证最小值必然从这组候选人中产生，于是每次只要从候选人中弹出最小的一个即可。
 
我们来选择第一组候选人，在这里可以选择第一列，因为每一个数字都是其对应行的最小值，全局最小值也必然在其中。然后使用ProrityQueue有序队列来存储这一组候选人，就能保证每次从队列中弹出的都是候选人中的最小值。
 例：
   选取以下矩阵，开始的候选人为第一列，然后每次选择候选人中的最小值弹出，然后被弹出的那一行的候选人右移以为记得到该行新的候选人，当某一行的值弹完后将候选人队列中长度减1即可，知道弹出第k-1个值，此时最小值队列的值即为所求第k小的值。
 
步骤如下图所示：
 
二分查找
 
思路及算法
 
由题目给出的性质可知，这个矩阵内的元素是从左上到右下递增的（假设矩阵左上角为 matrix[0][0]）。以下图为例：
 
 我们知道整个二维数组中 matrix[0][0] 为最小值，matrix[n−1][n−1] 为最大值，现在我们将其分别记作 l 和 r。
 
可以发现一个性质：任取一个数 mid 满足l≤mid≤r，那么矩阵中不大于 mid 的数，肯定全部分布在矩阵的左上角。
 
例如下图，取 mid=8：
 
 我们可以看到，矩阵中大于 mid 的数就和不大于 mid 的数分别形成了两个板块，沿着一条锯齿线将这个矩形分开。其中左上角板块的大小即为矩阵中不大于 mid 的数的数量。
 
我们只要沿着这条锯齿线走一遍即可计算出这两个板块的大小，也自然就统计出了这个矩阵中不大于mid 的数的个数了。
 
走法演示如下，依然取 mid=8：
 
 可以这样描述走法：
 
 1、初始位置在 matrix[n−1][0]（即左下角）；
  2、设当前位置为 matrix[i][j]。若 matrix[i][j]≤mid，则将当前所在列的不大于 mid 的数的数量（即 i+1）累加到答案中，并向右移动，否则向上移动；
  3、不断移动直到走出格子为止。
 
我们发现这样的走法时间复杂度为 O(n)，即我们可以线性计算对于任意一个 mid，矩阵中有多少数不大于它。这满足了二分查找的性质。
 
不妨假设答案为 x，那么可以知道 l≤x≤r，这样就确定了二分查找的上下界。
 
每次对于「猜测」的答案 mid，计算矩阵中有多少数不大于mid ：
 
如果数量不少于 k，那么说明最终答案 x 不大于 mid；
 如果数量少于 k，那么说明最终答案 x 大于 mid。
 这样我们就可以计算出最终的结果 x 了。
 
public int kthSmallest3(int[][] matrix, int k){
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, mid, k, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    //判断数量是否大于k
    public boolean check(int[][] matrix, int mid, int k, int n) {
        int i = n - 1;
        int j = 0;
        int num = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                num += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return num >= k;
    }
 
时间复杂度：O(nlog(r−l))，二分查找进行次数为 O(log(r−l))，每次操作时间复杂度为 O(n)。
 空间复杂度：O(1)。
 
暴力法：直接排序
 
public int kthSmallest(int[][] matrix, int k) {

        int rows = matrix.length;
        int columns = matrix[0].length;
        int []sorted = new int[rows*columns];
        int index = 0;
        for (int[] row : matrix) {
            for (int num : row) {
                sorted[index++] = num;
            }
        }
        Arrays.sort(sorted);
        return sorted[k-1];
    }
 
时间复杂度：O(n^2logn)，对 n^2个数排序。
 空间复杂度：O(n^2)，一维数组需要存储这 n^2个数。
 
暴力法容易理解，就是直接先把二维数组转换为一维数组，然后对该一维数组排序（调用Arrays.sort()函数即可），然后排序后数组中下标为k-1的值即为所求，但是这种方法没有用到有序数组的性质，而且新产生了一个n*n的一维数组，所以时间和空间复杂度都很高。
 
其它方法自行查看Leetcode官方题解。
 参考：
 Leetcode题解1
 Leecode官方题解

有序矩阵：每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 
有序查找用二分法较快，借用一张图说明思路：（原图地址：http://justjavac.iteye.com/blog/1310178）
 

 
 
 

  假设查找17，第一次比较10，然后比较25，然后比较13，返回元素13，这时候再递归查找13
 左下角的矩阵和右上角的矩阵就可以了（红色椭圆部分）
 

 
 
关键问题：什么时候停止二分？
 

 
 
从上面的图中可以总结出：
 
当二分结果不再发生变化（等于左上角，或等于右下角）时，即满足条件 (i==m1 || i ==m2) && (j==n1 || j==n2)时停止二分，并开始递归地二分查找左下矩阵和右上矩阵。
 
分为以下3种情况：
 
1）、
 
 
1
2
   

 
2）、
 
 
1
2
 
3）、
 
 
1
2
3
4
 

 总结二分停止时的所有(i,j)可能：
 
 
i
j
m1
n1
m1
n2
m2
n1
m2
n2
 

 

 
所以，while循环的条件设定为：  !((i==m1 || i ==m2) && (j==n1 || j==n2))

 

 
 
C实现（Time Limit Exceed）：
 

#include<stdio.h>
 
int matrix[1005][1005];
int binarySearch(int matrix[][1005], int x, int m1, int n1, int m2, int n2);
 
int main() {
    int m, n, i, j, x;
    while(scanf("%d %d", &m, &n) != EOF) {
        scanf("%d", &x);
        for(i = 0; i < m; i++) {
            for(j = 0; j < n; j++) {
                scanf("%d", &matrix[i][j]);
            }
        }
 
        int flag = binarySearch(matrix, x, 0, 0, m-1, n-1);
 
        if(flag) {
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
    return 0;
}
 
int binarySearch(int matrix[][1005], int x, int m1, int n1, int m2, int n2) {
    int leftResult = 0, rightResult = 0;
    if(matrix == NULL) {
        return 0;
    }
    if(x < matrix[m1][n1] || x > matrix[m2][n2]) {
        return 0;
    }
    else if(x == matrix[m1][n1] || x == matrix[m2][n2]) {
        return 1;
    }
 
    int i = (m1 + m2) / 2;
    int j = (n1 + n2) / 2;
 
    while(!((i == m1 || i == m2) && (j == n1 || j == n2))) {
        //printf("m1:%d, n1:%d, m2:%d, n2:%d, i:%d, j:%d, matrix[i][j]:%d\n", m1,n1,m2,n2,i,j,matrix[i][j]);
        if(x == matrix[i][j]) {
            return 1;
        }
        else if(x < matrix[i][j]) {
            i = (m1 + i) / 2;
            j = (n1 + j) / 2;
        }
        else {
            i = (i + m2) / 2;
            j = (j + n2) / 2;
        }
    }
 
    if(i < m2) {
        leftResult = binarySearch(matrix, x, i+1, n1, m1, j);
    }
    if(leftResult) {
        return 1;
    }
    if(j < n2) {
        rightResult = binarySearch(matrix, x, m1, j+1, i, n2);
    }
    if(rightResult) {
        return 1;
    }
 
    return 0;
}
 
/**************************************************************
    Problem: 1384
    User: wusuopuBUPT
    Language: C
    Result: Time Limit Exceed
****************************************************************/

 参考：
http://justjavac.iteye.com/blog/1310178
 
以上是二分查找的解法
 --------------------------------------------------------------------------------
 
方法二：不用递归，从矩阵的右上角(x,y)开始search（这样有一个好处：(x,y)的左侧所有点都小于matrxi[x][y], （x,y）的下侧所有点都大于matrix[x][y]），在每个点都做这样的判断：
 

if (a[i][j] == key)
	return 1;//找到，直接返回1
else if (a[i][j] < key)
	i++; //当前值小于key,则向下search
else
	j--; //当前值大于Key,则向左search

 
AC代码： 
 

 
 

#include<stdio.h>
 
int search(int a[][1005], int m, int n, int key) {
    int i = 0;
    int j = n - 1;
    while (i < m && j >= 0) {
        if (a[i][j] == key)
            return 1;
        else if (a[i][j] < key)
            i++;
        else
            j--;
    }
 
    return 0;
}
 
int main() {
    int n, m;
    int a[1005][1005];
    while (scanf("%d %d", &m, &n) != EOF) {
        int key;
        scanf("%d", &key);
        int i, j;
        for (i = 0; i < m; i++){
            for (j = 0; j < n; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        int flag = search(a, m, n, key);
        if(flag) {
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
    return 0;
}
 
/**************************************************************
    Problem: 1384
    User: wusuopuBUPT
    Language: C
    Result: Accepted
    Time:690 ms
    Memory:4788 kb
****************************************************************/
 

 
 参考： 
http://blog.csdn.net/shanshanpt/article/details/8685587
 
http://www.cnblogs.com/remlostime/archive/2012/11/21/2780352.html