查找算法

• 剑指offer03-数组中重复的数字
• • 思路：
  • 代码：
• 剑指offer53-I-在排序数组中查找数字
• • 思路
  • 代码
• 剑指offer53-II-0～n-1中缺失的数字
• • 思路
  • 代码

剑指offer03-数组中重复的数字

找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字
示例：
输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000

思路：

一开始没有顾忌时间和空间复杂度，想的是遍历数组，并用一个计数数组存储每个数字的个数，然后遍历寻找第一个个数超过2的数字。
后来考虑了一下时间复杂度，于是在第一次遍历计数时，找到第一个重复的数字就跳出循环并返回。

代码：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) 
    {
        int x=nums.size();
        int *array=new int[x];
        for(int i=0;i<x;i++)
        {
            array[i]=0;
        }
        int y;
        for(int i=0;i<x;i++)
        {
            y=nums[i];
            array[y]++;
            if(array[y]>=2)
                break;
        }
        return y;
    }
};
/*
执行时间：28ms;
内存消耗：23.3MB。
*/

查找算法

• 剑指offer03-数组中重复的数字
• • 思路：
  • 代码：
• 剑指offer53-I-在排序数组中查找数字
• • 思路
  • 代码
• 剑指offer53-II-0～n-1中缺失的数字
• • 思路
  • 代码

剑指offer53-I-在排序数组中查找数字

统计一个数字在排序数组中出现的次数。
示例1
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例2
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

思路

因为数组是按序列排好的，所以只要顺序遍历，用一个变量计数，一旦找到就累计；当不是且变量有过记录就证明计数结束，从而终止遍历；当没有找到，变量直到计数结束还是0。
感觉还可以用二分法，时间复杂度可以更低一些。

代码

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
    int num=0;
    int x=nums.size();
    for(int i=0;i<x;i++){
        if(nums[i]==target) num++;
        else if(num>0)
        break;
    }
    return num;
    }
};
/*
执行时间：8ms；
内存消耗：12.8MB。
*/

查找算法

• 剑指offer03-数组中重复的数字
• • 思路：
  • 代码：
• 剑指offer53-I-在排序数组中查找数字
• • 思路
  • 代码
• 剑指offer53-II-0～n-1中缺失的数字
• • 思路
  • 代码

剑指offer53-II-0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例1
输入: [0,1,3]
输出: 2
示例2
输入: [0,1,2,3,4,5,6,7,9]
输出: 8

思路

因为数组是有序的，所以直接遍历这个数组，直到被遍历的数字跟序号不一样，跳出循环，表示该序号是缺失数字；若循环到头，说明最后一个数字是缺失的。

代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int x=nums.size();
        int i;
        for(i=0;i<x;i++){
            if(nums[i]!=i)
            break;
        }
        return i;
    }
};
/*
执行时间：12ms；
内存消耗：16.7MB。
*/