数据结构算法题解大全【持续更新】（c++）

1、二维数组查找

题述

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

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M。

我的思路

• 该题中二维数组每行从左到右是递增的，每列从上到下是递增的。
• 起始指针从二维数组末尾行第一元素m开始，

1. 如果存在m>target，代表目标值小于此行任意一个元素，则可剔除m所在行，指针上移一行，
2. 如果存在m<target，因为指针是从左下角，即行首列尾出开始的，此时m所在列靠后元素已经查过，则查找m所在行即可
3. 如果相等则输出。

• 该题复杂度O(列宽+log行宽)

算法展示

删选+二分查找

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        //有序，从末尾行开始查找
        for(int i = (array.size()-1);i>=0;i--)
        {
                if(array[i][0]<target)//如果该行第一个元素小于目标值
                {
                        //二分查找当前行
                        int low,high,mid;
                        low = 0,high = (array[i].size()-1);
                        while(low<=high)
                        {
                                mid = (low/2+high/2);
                                if(array[i][mid]==target)return true;
                                else if(array[i][mid]<target)low = mid+1;
                                else high = mid-1; 
                        }
                         return false;
                }
        }
       
    }
};

暴力**

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        //有序，从末尾行开始查找
        for(int i = (array.size()-1);i>=0;i--)
        {
			for(int i = (array.size()-1);i>=0;i--)
        	{
    	    	  if(array[i][mid]==target)return true;
	    	}
       }	
       return false;     
    }
};