数字在排序数组中出现的次数

题目描述

给定一个有N×M的整型矩阵matrix和一个整数K，matrix每行每列都排好序了。
实现一个函数，判断K是否在matrix中。

分析

1. 从右上角的数开始寻找
2. 右上角比k小，说明k不可能在第一行了，看下面的行
3. 右上角比k大，说明k不可能在最后一列，看左边的列

代码实现

public class FindNumInSortMatrix {
	public static int[] find(int[][] matrix, int num) {
		// 1-----------------------------------------------------
		int a = 0;// 行
		int b = matrix[0].length - 1;// 列
		while (a < matrix.length && b > -1) {
			if (matrix[a][b] == num) {
				return new int[] { a, b };
			} else if (matrix[a][b] < num) { // 2-------------------------
				a++;// 往下一行走
			} else { // 3-----------------------------------------------------
				b--;// 往该列左走
			}
		}
		return new int[] { -1, -1 };
	}

	public static void main(String[] args) {
		int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
		int num1 = 5;
		int arr1[] = find(matrix, num1);
		System.out.println(num1 + "在" + (arr1[0] + 1) +"行" + (arr1[1] + 1) + "列");
		int num2 = 7;
		int arr2[] = find(matrix, num2);
		System.out.println(num2 + "在" + (arr2[0] + 1) +"行" + (arr2[1] + 1) + "列");
	}
}