做为一个通信工程专业的人，只做过嵌入式软件，对数据结构都还不够了解。现在拿起剑指offer开始刷算法题，真的感觉不太容易。讲一讲做的两道题，过程还蛮折磨人的。

  • 03数组中重复的数字
  • 04二维数组的查找

数组中重复的数字

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：2 <= n <= 100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

看到题目之后，想都没想就立马开始敲代码。看看我的第一段代码：

#define ERROR -1

int findRepeatNumber(int* nums, int numsSize)
{
    int i,j;
    for(i=0;i<numsSize;i++)
    {
        for(j=i+1;j<numsSize;j++)
        {
            if(nums[i] == nums[j])
                return nums[i];
        }
    }
    return ERROR;
}

这几乎是最简单直接，不用动脑的方法了。但它的时间复杂度是有蛮高的，几乎达到了O(n^2)，果然在n=9000的事例中超出时间限制。而且也没有考虑程序的鲁棒性，算是很低级的解法了。

第二段代码是，学习书上的交换数据元素的方式来解。考虑了空指针、数据元素等负面条件，考虑了程序的鲁棒性，应该是非常好的解法了。

#define ERROR -1

int findRepeatNumber(int* nums, int numsSize)
{
    if(nums == NULL || numsSize <= 0)
        return ERROR;
    
    for(int i = 0; i<numsSize; i++)
    {
        if(nums[i]<0 || nums[i]>numsSize-1)
            return ERROR;
    }

    for(int i = 0; i<numsSize; i++)
    {
        while(nums[i] != i)
        {
            if(nums[i] == nums[nums[i]])
                return nums[i];

            int a = nums[i];
            nums[i] = nums[a];
            nums[a] = a;
        }
    }
    return ERROR;
}

第三段程序是，书上有所提示的hash表的方式。没有打乱数组原有的顺序，但是新建hash表回占用部分内存，算是用空间换取时间的求解方式。

#define ERROR -1

int findRepeatNumber(int* nums, int numsSize)
{
    int hash[numsSize];

    if(nums == NULL || numsSize <= 0)
        return ERROR;
	
	for(int i = 0; i<numsSize; i++)
    {
        if(nums[i] < 0 || nums[i] > numsSize-1)
            return ERROR;
    }

    for(int i=0; i<numsSize; i++)
    {
        if(hash[nums[i]] != 1 )
        {
            hash[nums[i]] = 1;
        }
        else 
            return nums[i];
    }
    return ERROR;
}

第四段程序，是参考书上的二分法的方式，既不打乱原有的数组元素，也不用创建新的数组占用空间。但是这个算法好像有问题。

#define ERROR -1

int CountRange(const int *nums, int numsSize,int start, int end)
{
    int count = 0;

    for(int i=0; i<numsSize;i++)
    {
        if(nums[i] >= start && nums[i] <= end)
            count++;
    }
    return count;
}

int findRepeatNumber(int* nums, int numsSize)
{
    int start = 0;
    int end = numsSize-1;
    
    while (end >= start)
    {
        int middle = ((end-start)>>1)+start;
        int count = CountRange(nums, numsSize, start, middle);

        if(end == start)
        {
            if(count>1)
                return start;
            else 
                break;
        }

        if(count > (middle - start + 1))
            end = middle;
        else 
            start = middle + 1;
    }
    return ERROR;
}

输入：[0, 1, 2, 0, 4, 5, 6, 7, 8, 9]

输出：ERROR

预期结果：0

因为在中点的时候start-middle和middle-end的count都是5，程序就看后面半段是否有重复的元素了。尔重复的元素在前面半段就被忽略掉了，所以输出为ERROR。所以这个算法还是有问题，需要改进呀。

二维数组的查找

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

示例:

现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。

给定 target = 20，返回 false。

限制：0 <= n <= 1000 ；0 <= m <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof

bool findNumberIn2DArray(int** matrix, int matrixSize, int* matrixColSize, int target)
{
    int cow = 0;
    int col = *matrixColSize - 1;

    if(matrix == NULL || matrixSize <= 0 || *matrixColSize <= 0)
    {
        return false;
    }
 
    while(cow < matrixSize && col >= 0)
    {
        if(matrix[cow][col] > target)
        {
            col--;
        }
        else if(matrix[cow][col] < target)
        {
            cow++;
        }
        else
        {
            return true;
        }
    }
    return false;
}

这道题的思路是：将一个复杂问题，通过分析一个简单具体的例子，来寻找普遍的规律。这是将矩阵右上角的数字元素与目标数字进行对比，依次删除列和行，直至找到相等的元素或遍历完整个矩阵。就像下面所示的步骤。

img

第一遍的时候，在输入矩阵[]的时候，总是出错。还是边界条件、负面条件没有考虑到，还是要多考虑程序的鲁棒性。

初刷算法，深刻感受到以前写代码的粗糙，代码的鲁棒性做的比较差，只考虑到最理想输入的情况。

想要成为一名优秀的程序员，以后还要多注意代码的鲁棒性！