西安做网站友情链接的概念

（小米真题）
题目：有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。
要求：时间复杂度小于O(N)

构建一个8*8的杨氏矩阵

// 生成杨氏矩阵
public static int[][] generateRandomYoungTableau(int n) {int[][] matrix = new int[n][n];Set<Integer> usedNumbers = new HashSet<>();Random random = new Random();for (int i = 0; i < n; i++) {Set<Integer> rowNumbers = new HashSet<>();for (int j = 0; j < n; j++) {int number;do {number = random.nextInt(n * n) + 1; // 生成1到n*n之间的随机数} while (usedNumbers.contains(number) || rowNumbers.contains(number));usedNumbers.add(number);rowNumbers.add(number);matrix[i][j] = number;}}// 对每一行进行排序以满足杨氏矩阵的性质for (int i = 0; i < n; i++) {Arrays.sort(matrix[i]);}// 对每一列进行排序以满足杨氏矩阵的性质for (int j = 0; j < n; j++) {int[] column = new int[n];for (int i = 0; i < n; i++) {column[i] = matrix[i][j];}Arrays.sort(column);for (int i = 0; i < n; i++) {matrix[i][j] = column[i];}}return matrix;
}

杨氏数组中查找

// 杨氏数组中查找
// 这里采取从右上角的数字进行查找的方式
// 利用杨氏数组的特性，每一次比较右上角的值都可以去掉一行或者一列
private static boolean queryInYoungTableau(int[][] matrix, int search) {boolean flag = false;int row = 0;int column = matrix[0].length - 1;while (row < matrix.length && column >= 0) {int temp = matrix[row][column];if (temp == search) {flag = true;break;} else if (temp > search) {// 去掉列column--;} else {// 去掉行row++;}}return flag;
}

测试

public static void main(String[] args){int n = 8; // 矩阵的大小int[][] matrix = generateRandomYoungTableau(n);// 打印生成的杨氏矩阵for (int[] row : matrix) {System.out.println(Arrays.toString(row));}// 判断给定的数字是否存在于 杨氏矩阵中int search = 68;boolean exists = queryInYoungTableau(matrix, search);System.out.printf("%s是否存在于杨氏矩阵中：%s%n", search, exists);
}

测试结果：

但我这个杨氏数组不是很规范，这里面最大的值也就是64了，后面优化一下这个生成杨氏数组的方法