今天在leetcode上刷了两道查找题，感觉其中可优化的点还挺多的。

一维数组查找

0~n-1中缺失的数字

题目：一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

分析：做这道题的时候我首先想到的是像快排那样二分查找，不过仅需要照顾一端的就好了，关键在于理清find递归的区间，时间复杂度为O(nlogn)。运行速度12ms，超过了86.18%的c++用户.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int find(vector<int>& nums,int l,int r)
{
    if(l==r+1)
    {
        return l;
    }
    if(nums[(l+r)/2]==(l+r)/2)
    {
        return find(nums,(l+r)/2+1,r);
    }
    else{
        return find(nums,l,(l+r)/2-1);
    }
}

其实如果用数学方法直接累加会更方便，哈希表也行，但运行速度没二分查找快，这两个都要遍历整个数组。

二维数组查找

二维数组的查找

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

分析：这个二维数组的规律是每个元素的左上都是不大于它的，右下都是不小于它的。最开始我是想仿照一维那样用二分递归，发现两个递归式的前后后导致查找的方向有偏向，使得左下角或右上角最后再查找到。最后我想到以前做迷宫题的时候的方法，用队列存储查找的下一个节点，这样就能从左上角开始同时照顾左右地往右下角探查。但最终的运行时间仅超过了5.27%的用户。代码较长就不放出污染眼睛了。
最后查找题解，发现Z型查找的速度是比较快的，它的思路是像二叉搜索树那样把右上角的元素作为根节点，左孩子是不大于它的，右孩子是不小于它的，一直找到最后，本质上还是二分查找。时间复杂度是O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
    if(matrix.size()==0) return false;
    int root_i = 0;
    int root_j = matrix[0].size()-1;
    bool tag = false;
    while(root_i<matrix.size()&&root_j>=0){
        if(matrix[root_i][root_j]>target) root_j--;
        else if(matrix[root_i][root_j]<target) root_i++;
        else{
            tag=true;
            break;
        }
    }
    return tag;
}

小结

今天刷的题这两道是给我印象较深的，其中一个原因是它们的数组都是用容器二维基础数据类型，一维的还好，二维容器我还没怎么见过，今天算是练了练手，两道查找题的思想都是利用二分，虽然方法不太一样