题解 | JAVA #矩阵元素查找# [P3]

首先，两点可以确定一个矩形(i.e. 左上+右下)
设左上+右下两点囊括的矩形为M (M初始为整个mat)

不停的去通过比较x与M的右上和左下角的数值的大小，来缩小M的大小。
 x > M右上角, topLeft.row++
 x < M右上角, botRight.col--
 x > M左下角 topLeft.col++
 x < M左下角, botRight.row--

当M缩成一个点时(i.e. 左上==右下)，这个点就是答案

举例，以下矩形找5：
1  2  6
4  5  10
7  8  11

loop   左上    右下
初始：[0, 0]  [2, 2]
 1:  [0, 0]  [1, 1]
 2:  [1, 1]  [1, 1]  -> 输出[1, 1] = 5

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
      int[] topLeft = new int[]{0,0};
      int[] botRight = new int[]{n-1, m-1};
      
      while (topLeft[0] != botRight[0] ||
             topLeft[1] != botRight[1]) {
        if (x > mat[topLeft[0]][botRight[1]])
          topLeft[0]++;
        if (x > mat[botRight[0]][topLeft[1]])
          topLeft[1]++;
          
        if (x < mat[botRight[0]][topLeft[1]])
          botRight[0]--;
        if (x < mat[topLeft[0]][botRight[1]])
          botRight[1]--;
      }
      
      return topLeft;
    }
}