数组——二维数组中的查找

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

代码实现

import java.util.Scanner;


public class Solution {

public static void main(String[] args) {

@SuppressWarnings("resource")
        Scanner in = new Scanner(System.in);

        Solution solution = new Solution();

int[][] sourceArray = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

        System.out.print("请输入一个整数：");
int source = in.nextInt();

        System.out.println("该整数在对应的数组中：" + solution.Find(source, sourceArray));
    }

/**
 * 自己的解法，一点都不推荐 
 * 
 * @param target
 * @param array
 * @return
 */
// public boolean Find(int target, int[][] array) {
// 
// //遍历数组，并将数组中的每一个元素与指定的整数比较
// for(int i = 0; i < array.length; i++) {
// for(int j = 0; j < array[i].length; j++) {
// if(target == array[i][j]) return true;
// }
// }
// 
// return false;
// }

/**
 * 推荐解法 1 ：二分查找
 * 
 * 把每一行看成有序递增的数组，利用二分查找，通过遍历每一行得到答案，时间复杂度是nlogn
 * 
 * @param target
 * @param array
 * @return
 */
// public boolean Find(int target, int[][] array) {
// 
// for(int i = 0; i < array.length; i++){
// 
// int low = 0; 
// int high = array[i].length - 1;
// 
// while(low <= high){
// int mid = (low + high) / 2; //二分查找的中点
// if(target > array[i][mid]) low = mid + 1; //目标值大于中点值，低点后移
// else if(target < array[i][mid]) high = mid - 1; //目标值小于中点值，高点前移
// else return true; //目标值等于中点值
// }
// 
// }
// 
// return false;
// 
// }

/**
 * 推荐解法 2：类似于二分查找
 * 
 * 
 * 利用二维数组由上到下，由左到右递增的规律，那么选取右上角或者左下角的元素a[row][col]与target进行比较，
 * 
 * 右上角：
 * 当target小于元素a[row][col]时，那么target必定在元素a所在列的左边，即col--；
 * 当target大于元素a[row][col]时，那么target必定在元素a所在行的下边，即row++；
 * 
 * 左下角：
 * 当target小于元素a[row][col]时，那么target必定在元素a所在行的上边，即row--；
 * 当target大于元素a[row][col]时，那么target必定在元素a所在列的右边，即col++；
 * 
 * @param target
 * @param array
 * @return
 */
public boolean Find(int target, int[][] array) {

//选择右上角
int row = 0;
int col = array[0].length - 1;

while(row <= array.length - 1 && col >= 0){
if(target == array[row][col]) return true;
else if(target > array[row][col]) row++;
else col--;
        }

return false;

    }

}