首页 > 试题广场 >

二维数组中的查找

[编程题]二维数组中的查找
  • 热度指数：2367261 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 ， 矩阵中的值满足
进阶：空间复杂度 ，时间复杂度
示例1

输入

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

true

说明

存在7，返回true
示例2

输入

1,[[2]]

输出

false
示例3

输入

3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

false

说明

不存在3，返回false
算法知识视频讲解
查看答案及解析
添加回答
推荐
徘徊的路人甲头像 徘徊的路人甲 
/* 思路
* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
* 因此从左下角开始查找，当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时，上移
*/

class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        int rowCount = array.size();
        int colCount = array[0].size();
        int i,j;
        for(i=rowCount-1,j=0;i>=0&&j<colCount;)
        {
            if(target == array[i][j])
                return true;
            if(target < array[i][j])
            {
                i--;
                continue;
            }
            if(target > array[i][j])
            {
                j++;
                continue;
            }
        }
        return false;
    }
};

编辑于 2015-06-18 16:50:07 回复(249)
C
想玩飞盘的小龙虾面试中头像 想玩飞盘的小龙虾面试中
有没有大佬看看是出了什么问题了
您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起
您可以用printf在函数中打印信息分析问题

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param target int整型
 * @param array int整型二维数组
 * @param arrayRowLen int array数组行数
 * @param arrayColLen int* array数组列数
 * @return bool布尔型
 */
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen )
{
    // write code here
    int fir1=1,fir2=0,sec1=arrayRowLen,sec2=*arrayColLen-1;
    int mn1=arrayRowLen>*arrayColLen?*arrayColLen:arrayRowLen;
    while(mn1--)
    {
        if(array[fir1][fir2]==target) return true;
        else if(array[fir1][fir2]>target)
        {
            fir1--;
            fir2--;
            break;
        }
        else if(array[fir1][fir2]<target)
        {
            fir1++;
            fir2++;
        }
    }
    int mn2=arrayRowLen>*arrayColLen?*arrayColLen:arrayRowLen;
    while(mn2--)
    {
        if(array[sec1][sec2]==target) return true;
        else if(array[sec1][sec2]>target)
        {
            sec1++;
            sec2++;
            break;
        }
        else if(array[sec1][sec2]<target)
        {
            sec1--;
            sec2--;
        }
    }
    int opt1=fir2<sec2?fir2:sec2;
    int opt2=fir2>sec2?fir2:sec2;
    int opt3=fir1<sec1?fir1:sec1;
    int opt4=fir1>sec1?fir1:sec1;
    for(int i=opt3;i<=opt4;i++)
    {
        for(int j=opt1;j<=opt2;j++)
        {
            if(array[i][j]==target) return true;
        }
    }
    return false;
}










发表于 2023-11-07 20:29:18 回复(0)
C
A202302282044461头像 A202302282044461
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
    int left = 0, right = *arrayColLen - 1;
    while (left < arrayRowLen && right > -1) {
        if (target == array[left][right]) {
            return true;
        }
        if (target < array[left][right]) {
            right--;
        }
        if (target > array[left][right]) {
            left++;
        }  
    }
    return false;
}
发表于 2023-09-09 14:42:54 回复(0)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param target int整型
 * @param array int整型二维数组
 * @param arrayRowLen int array数组行数
 * @param arrayColLen int* array数组列数
 * @return bool布尔型
 */
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen )
{
    // write code here
    int midc=0;
    int midr=0;

    while(midr<arrayRowLen)
    {
        int left=0;
        int right=*arrayColLen-1;
        while(midr<arrayRowLen)
        {
            if(target>=*(*(array+midr))&&target<=*(*(array+midr)+*arrayColLen-1))
            {
                break;
            }
            ++midr;
        }
        if(midr>=arrayRowLen)
        {
            return false;
        }
        while(left<=right)
        {
            midc=left+(right-left)/2;
            int p=*(*(array+midr)+midc);
            if(target==p)
            {
                return true;
            }
            else if(target<p)
            {
                right=midc-1;
            }
            else if(target>p)
            {
                left=midc+1;
            }
        }
        ++midr;
    }

    return false;
}
发表于 2023-07-03 17:59:10 回复(0)
C
小小小孩头像 小小小孩 
#include <stdbool.h>
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) 
{
    // write code here
    if(array == NULL ||arrayRowLen == 0 || *arrayColLen == 0)
        return false;
    int row=0,col=*arrayColLen-1;
    while(row<arrayRowLen&&col>=0)
    {
        if(array[row][col]>target)
            col--;
        else if(array[row][col]<target)
            row++;
        else if(array[row][col]==target)
            return true;
    }
    return false;
}

发表于 2023-05-27 00:38:52 回复(0)
C
yyfan98头像 yyfan98
思路：每行进行二分查找 
#include <stdbool.h>

bool FindArray (int* array, int target, int length) {
    int left = 0;
    int right = length - 1;
    int middle;
    #if 0
    for (int i = 0; i < length; i++) {
        printf("%d ", array[i]);
    }
    putchar('\n');
    #endif
    while (left <= right) {
        middle = (left + right) /2;
        //printf("%d", target);
        if (array[middle] > target) {
            right = middle - 1; 
        } else if (array[middle] < target) {
            left = middle + 1;
        }

        if (array[middle] == target)
            return true;
    }
    return false;
}
// 1 2 8 9
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    bool isFind = false;

    for (int i = 0; i < arrayRowLen; i++) {
        isFind = FindArray(*(array + i), target, *arrayColLen);
        if (isFind == true) 
            break;
    }
    return isFind;
    
}


发表于 2023-03-25 17:35:51 回复(0)
C
会飞的芜香蛋头像 会飞的芜香蛋
找出行和列中大的一个，比较每行/列最后一个元素（该行/列最大的元素），找到第一个大于或等于target的元素位置从该行/列开始进行二分查找。
时间复杂度为O(nlogn) 
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    int i = 0;
    if (arrayRowLen < *arrayColLen) {//行大于列
        for (i; i < arrayRowLen; i++) {//从每列最后一个元素开始找出第一个大于或等于target
            if (array[i][*arrayColLen - 1] == target)
                return 1;
            if (array[i][*arrayColLen - 1] > target)
                break;
        }
        for (i; i < arrayRowLen; i++) {//从该列开始进行二分查找
            int low = 0, high = *arrayColLen - 1;
            while (low <= high) {
                int mid = (low + high) / 2;
                if (array[i][mid] == target)
                    return 1;
                else if (array[i][mid] > target)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
        }
    }
    else {//列大于或等于行
        for (i; i < *arrayColLen; i++){//从每行最后一个元素开始找出第一个大于或等于target
            if (array[arrayRowLen - 1][i] == target)
                return 1;
            if (array[arrayRowLen - 1][i] > target)
                break;
        }
        for (i; i < *arrayColLen; i++) {//从该行开始进行二分查找
            int low = 0, high = arrayRowLen - 1;
            while (low <= high) {
                int mid = (low + high) / 2;
                if (array[mid][i] == target)
                    return 1;
                else if (array[mid][i] > target)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
        }
    }
    return 0;
}



发表于 2023-02-10 15:38:07 回复(0)
C
算帝头像 算帝 
bool Find(int target, int** array, int rn, int* cn ) {
    int i = rn - 1, j = 0;
    while(i >= 0 && j <= *cn-1)  {
        if(array[i][j] == target) return true;
        else if(array[i][j] < target) {
            j++;
        } else {
            i--;
        }
    }
    return false;
}
发表于 2023-01-10 20:32:57 回复(0)
C
all-in秋招的打工人很失落头像 all-in秋招的打工人很失落
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
    int i, j;
    for(i=0;i<arrayRowLen;++i){
        for(j=0;j<* arrayColLen;++j){
            if(array[i][j]==target) return true;
            else if(array[i][j]>target) break;
        }
    }
    return false;
}
发表于 2023-01-06 22:05:19 回复(0)
C
说又不是不能用的小疯子很豁达头像 说又不是不能用的小疯子很豁达
完全个笨办法，但是要理解二级指针array以及指针arrayColLen的含义
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    int r = arrayRowLen;
    int c = *arrayColLen;
    int p = 0,  q = 0;
    while (p >= 0 && p <= r - 1)  {
        while (q >= 0 && q <= c - 1) {
            if (array[p][q] == target) {
                return true;
            
            }else 
            q++;

        }
        p++;
        q=0;

    }
    return false;
}
发表于 2022-12-10 14:29:47 回复(0)
C
80后大叔头像 80后大叔
思路是当前坐标点如果小于target，则先向右移动，判断右侧数字是否大于target，小于则移动，直到到达最右侧。否则向下移动。
如果当前坐标点数字大于target，则向左移动
直到找到target，返回true。坐标超出数组的话表示遍历完全都没找到，返回false
```
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
    int m = arrayRowLen;
    int n = *arrayColLen;
    int p=0,q=0;
    while((p>=0 &&p<=m-1) && (q>=0 && q<=n-1)) {
        if(array[p][q] == target) return true;
        else if(array[p][q]<target){
            if(q<n-1 && array[p][q+1]<=target) q++;
            else p++;
        } else {
            q--;
        }
    }
    return false;
}

```
发表于 2022-11-28 23:43:14 回复(0)
C
取nm名字全被取了头像 取nm名字全被取了 
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) 
{
    int row = 0,col = *arrayColLen - 1;
    while(row < arrayRowLen && col > -1)
    {
        if(array[row][col] < target)
        {
            row++;
        }
        else if(array[row][col] > target)
        {
            col--;
        }
        else
        {
            return true;
        }
    }
    return false;
    // write code here
}

发表于 2022-11-04 17:46:31 回复(0)
C
牛客256350437号头像 牛客256350437号
    if (arrayRowLen == 0) {
        return 0;
    }

    for (int i = 0; i < arrayRowLen; ++i) {
        for (int j = 0; j < *arrayColLen; ++j) {
            if (*(*(array + i) + j) == target) {
                return 1;
            }
        }

    }

    return 0;
发表于 2022-10-23 21:28:10 回复(0)
C
牛客664878431号头像 牛客664878431号
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param target int整型 
 * @param array int整型二维数组 
 * @param arrayRowLen int array数组行数
 * @param arrayColLen int* array数组列数
 * @return bool布尔型
 */
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
   int n = arrayRowLen;
    int m = *arrayColLen;
    int j = 0;
    for (int i = 0; i<n*m&&j<*arrayColLen; i++)
    {
        if(n<0||j<0||n>arrayRowLen||j>(* arrayColLen)-1)
    {   
          return false;
    }
        if (array[n-1][j]>target)
        {
            n--;
            if(-1==n)
            {
                return false;
            }
        }
        if (array[n-1][j]<target)
        {
            j++;
            if(j>(*arrayColLen-1))
            {
                return false;
            }
        }
        if (array[n-1][j]==target)
        {
            return true;
        }

        
    }
    return false;
}





我这这只有19组通过，它显示又2组堆栈溢出，有没有大佬帮我看看
发表于 2022-10-11 22:22:28 回复(0)
C
牛客677160630号头像 牛客677160630号 
将二级指针看成一个一维的指针数组，存放的是指向一维数组的地址
每层使用二分查找
bool search(int* arr,int target,int arrayColLen)
{
    int left=0,right=arrayColLen-1;
    int mid=0;
      while(left<=right)
        {
            mid=left+(right-left>>1);
            if(arr[mid]>target)
            {
                right=mid-1;
            }
            else if(arr[mid]<target)
            {
                left=mid+1;
            }
            else
            {
                return true;
            }
        }
    return false;
}
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
   while (arrayRowLen--)
    {
        if (search(*array, target, *arrayColLen))
        {
            return true;
        }
        array++;
    }
    return false;
}

发表于 2022-07-31 21:52:45 回复(0)
C
java顶级猎手头像 java顶级猎手
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    for (int i=0;i<arrayRowLen;i++){
        for(int j =0;j<arrayColLen[i];j++){
            if(target == array[i][j]){
                return true;
            }
        }
    }
    return false;
}
发表于 2022-05-17 09:02:49 回复(0)
C
这世界那么多人头像 这世界那么多人
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
    int iRow = arrayRowLen - 1;    //行，从左下角开始查找
    int jCol = 0;    //列
    if(array == NULL)
        return false;
    
    while(iRow >= 0 && jCol < (*arrayColLen))
    {
        if(target == array[iRow][jCol])
        {
            return true;
        } else if(target > array[iRow][jCol])
        {
            jCol++;    //向右查找
        } else 
        {
            iRow--;    //向上查找
        }
    }
    return false;
}
发表于 2022-05-07 00:06:08 回复(0)
C
✨LAUGH头像 ✨LAUGH 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param target int整型 
 * @param array int整型二维数组 
 * @param arrayRowLen int array数组行数
 * @param arrayColLen int* array数组列数
 * @return bool布尔型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
#include<stdbool.h>
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
    int left=arrayRowLen-1;
    int down=0;
    while(down<*arrayColLen&&left>=0){
        if(array[left][down]<target)
            down++;
        else if(array[left][down]>target)
            left--;
        else return true;
    }
    return false;
}
发表于 2022-05-06 15:16:12 回复(0)
C
【社会人】头像 【社会人】 
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen )
{
    // write code here
    bool found=false;
         int len=*arrayColLen-1;
            int row=0;
            while(row<arrayRowLen&&len>=0)
            {
                if(array[row][len]==target){
                    found=true;
                    return found;
                    break;
                }
                if(array[row][len]>target){
                    len--;
                }
                if(array[row][len]<target){
                    row++;
                }
            }
   return false;
}

发表于 2022-03-18 11:56:37 回复(0)
C
拓跋友友头像 拓跋友友 
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) 
{
    int a=arrayRowLen;
    int b=*arrayColLen;
    // write code here
    for(int i=0;i<a;i++)
    {
        for(int j=0;j<b;j++)
        {
            if(*(*(array+i)+j)==target)
            {
                return true;
            }
        }
    }
    return false;
}

发表于 2022-03-17 21:13:25 回复(1)
提交观点

问题信息

数组
来自：2015年度信息化技能...
难度：
21条回答 1521000浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号