阅读量:3
1.题目要求:
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。
实列:
2.各位大佬们,大家好,此题我用的方法是一行一行的找,虽然比较繁琐,但也容易理解:
1.首先我们创建一个能在一行中遍历的函数:
int search(int* arr,int col,int target) { int left = 0; int right = col - 1; while(left <= right){ int mid = (left + right) / 2; if(target == arr[mid]){ return 1; }else if(arr[mid] < target){ left = mid + 1; }else{ right = mid - 1; } } return -1; }
其实这也相当于二分查找;
2.用循环把每一行的数传入函数中:
int i = 0; int col = *matrixColSize; for(i = 0;i < matrixSize;i++){ int res = search(matrix[i],col,target); if(res == 1) return true; } return false;
以下代码块为全部代码:
int search(int* arr,int col,int target) { int left = 0; int right = col - 1; while(left <= right){ int mid = (left + right) / 2; if(target == arr[mid]){ return 1; }else if(arr[mid] < target){ left = mid + 1; }else{ right = mid - 1; } } return -1; } bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){ int i = 0; int col = *matrixColSize; for(i = 0;i < matrixSize;i++){ int res = search(matrix[i],col,target); if(res == 1) return true; } return false; }
好了,这就是我的代码了,大家如果觉得好的话,就给个免费的赞吧,谢谢了^ _ ^