本文共 1139 字,大约阅读时间需要 3 分钟。
题目描述:在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
[ [1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15] ] 给定 target = 7,返回 true。 给定 target = 3,返回 false。 看到这个题,最简单的想法就是,挨个遍历,比较是否与目标值相等;显然复杂度很高,而且遗漏了一个很重要的条件,有序!故另外一种思路就是,每次比较最右列元素,若比target大,则列往前移动,反之,行往下移动,直到找到数据。
或者,看到有序,我们想到了二分查找,我们在固定到某一行的时候,利用二分法来找到目标值。// 解法1: bool Find(int target, vector> array) { int rows = array.size(); int cols = array[0].size(); for(int i = 0; i < rows; i++){ for(int j = 0; j < cols; j++){ if(array[i][j] == target) return true; } } return false; }
// 解法2bool Find(int target, vector> array) { int rows = array.size(); int cols = array[0].size(); int row = 0, col = cols - 1; while(row < rows && col >= 0){ if(array[row][col] == target) return true; else if(array[row][col] > target) col--; else row++; } return false; }
转载地址:http://uqwki.baihongyu.com/