C/C++教程

记录一下leetcode刷题-剑指offer(4)

本文主要是介绍记录一下leetcode刷题-剑指offer(4),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

查找算法

  • 剑指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。
*/
这篇关于记录一下leetcode刷题-剑指offer(4)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!