【感悟《剑指offer》典型编程题的极练之路】01数组篇！

                                                    个人主页：秋风起，再归来~

                                                文章所属专栏：《剑指offer》典型编程题的极练之路

  个人格言：悟已往之不谏，知来者犹可追

          克心守己，律己则安！

编辑

一、面试题1：数组中重复的数字（查重）

1.1 题目一：找出数组中重复的数字

1.2 题目二：不修改数组找出重复的数字

二、面试题2：二维数组中的查找

三. 完结散花

一、面试题1：数组中重复的数字（查重）

1.1 题目一：找出数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围：0≤n≤10000

进阶：时间复杂度 O(n) ，空间复杂度O(n)

示例：
输入：
[2,3,1,0,2,5,3]
返回值：
2
说明：
2或3都是对的 
牛客网上该题目链接（点击进入）

1.1.1排序法

解决这个问题我们首先可以想到一个非常简单的方法就是把数组进行排序，从有序的数组中找出重复的元素是一件很容易的事情，只需要从头到尾扫描排序后的数组就可以了。排序一个长度为n的数组需要O(nlongn)的时间

1.1.2 哈希表

我们还可以用哈希表来解决这个问题。从头到尾按顺序扫描数组的每个数字，每扫描到一个位置的时候，都可以用O(1)的时间来判断哈希表里是否已经包含了该数字。如果哈希表里还没有这个数字，就把他加入哈希表。如果哈希表里已经存在该数字，就找到一个重复的数字。这个算法的时间复杂度是O(n)，但它提高效率是以一个大小为O(n)的哈希表为代价的。

1.1.3 下标索引

我们注意到数组中的数字都在0~n-1的范围内。如果数组中没有重复的数字，那么排序后数字i将出现在下标为i的位置。由于数组中有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有位置。

现在我们重新排列一下这个数组。从头到尾依次扫描数组中的每一个数组，当扫描到下标为i的数字（m）时，如果这个数字等于i(m=i)，则我们接着扫描下一个数字，如果不是，那我们就把它（m）和下标为m的那个元素先进行比较，如果m与下标为m的元素的大小相等，那这个数（m）就是重复的数字，如果不相等，那我们就将这两个数字进行交换（即把m放到下标为m的位置）。接下来我们就重复这个比较交换的动作，直到我们发现一个重复的数字。

画个图理解一下：

牛客网上解题的代码如下~

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @return int整型
 */
int duplicate(int* numbers, int numbersLen ) {
    // write code here
    if(numbers==NULL||numbersLen<=0)
    return -1;
    //第一层循环遍历数组元素
    for(int i=0;i<numbersLen;i++)
    {
        //第二层循环将该元素放到和其值相等的下标的位置
        while(numbers[i]!=i)
        {
            if(numbers[i]==numbers[numbers[i]])
            {
                return numbers[i];
            }
            int tmp= numbers[i];
            numbers[i]=numbers[tmp];
            numbers[tmp]=tmp;
        }
    }
    return -1;
}

代码中尽管有两重循环，但每个数字最多只要交换两次就能找到属于他自己的完位置，因此总的时间复杂度为O(n)。另外，所有的操作都是在原数组上完成的，不需要分配额外的内存空间，所以空间复杂度为O(1)。

1.2 题目二：不修改数组找出重复的数字

题目描述：

在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。

例如：如果输入长度为8 的数组{2,3,5,4,3,2,6,7}，那么对应输出的是重复的数字是2或3。

1.2.1 创建临时数组

不能修改临时数组，那我们就创建一个临时的大小为n+1的数组，将原数组中数字为m的元素复制放到临时数组下标为m的位置上，在放入之前我们比较一下它们的值是否相等就可以很容易的找到重复的数字了。不过我们创建了一个大小为n+1的数组，所以这种算法的空间复杂度为O(n)，时间复杂度也是O(n)。

那我们接下来就尝试避免使用O(n)的空间看能不能解题~

1.2.2 二分查找

我们假设数组中没有重复的数字，那么对于1~n范围内的数字，我们在遍历原数组后，这些数字出现的次数一定为n，但如果原数组中有重复的数字并且在1~n内存在原数组中重复的数字，我们在遍历原数组后，这些数字出现的次数一定大于n。

所以，基于以上的分析，我们不妨借鉴二分查找法的思路将将我们要查重的数据一分为二来查找。

下面举一个栗子进行分析啦~

代码实现如下~

int countrange(int*numbers,int numbersLen,int start,int middle)
 {
    int count=0;
    for(int i=0;i<numbersLen;i++)
    {
        if(numbers[i]>=start&&numbers[i]<=middle)
        {
            count++;
        }
    }
    return count;
 }
int duplicate(int* numbers, int numbersLen ) {
    // write code here
    if(numbers==NULL||numbersLen<=0)
    return -1;
    int start=0;
    int end=numbersLen-1;
    while(start<=end)
    {
        int middle=((end-start)>>1)+start;
        //计算局部范围内数字出现的次数
        int count=countrange(numbers,numbersLen,start,middle);
        if(start==end)//找到最后一个数
        {
            if(count>1)
            return start;
            else
            break;
        }
        if(count>(middle-start+1))//前半段有重
        {
            end=middle;
        }
        else //后半段有重
        {
            start=middle+1;
        }
    }
    return -1;
}

需要指出的是上述代码按照二分查找的思路，如果输入长度为n的数组，那么函数countrange将被调用O(logn)次，每次需要O(n)的时间，因此总的时间复杂度为O(nlogn)，空间复杂度为O(1)。和前面提到的需要O(n)的辅助空间的算法相比，这种算法相当于以时间换空间

二、面试题2：二维数组中的查找

题目描述：

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

力扣上的题目链接（点击进入）

在具有上述特性的矩阵中搜索目标值的问题可以使用一种高效的算法来解决，这种算法的时间复杂度为O(m + n)。这个算法的基本思想是，从矩阵的右上角或左下角开始搜索，然后利用矩阵的特性来决定下一步的搜索方向。

以下是基于右上角开始搜索的算法步骤：

初始化一个指针，指向矩阵的右上角元素（即第一行最后一列的元素）。
比较当前指针指向的元素与目标值的大小：
- 如果当前元素等于目标值，则搜索成功，返回该元素的位置。
- 如果当前元素大于目标值，由于矩阵的每一列都是升序排列的，因此目标值不可能在当前列的更下方位置，所以将指
- 针向左移动一列。
- 如果当前元素小于目标值，由于矩阵的每一行都是升序排列的，因此目标值不可能在当前行的更左侧位置，所以将指针向下移动一行。
重复步骤2，直到找到目标值，或者指针移出矩阵的范围（即指针指向的行列号超出矩阵的边界）。如果指针移出矩阵范围仍未找到目标值，则搜索失败，返回相应的结果。

解题的具体代码如下~

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    if(matrix==NULL||matrixSize<=0)
    return false;
    int row=0;//从第0行
    int col=(*matrixColSize-1);//从最后一列
    while(row<matrixSize&&col>=0)
    {
        if(matrix[row][col]==target)
        return true;
        else if(matrix[row][col]<target)
        row++;
        else
        col--;
    }
    return false;
}