剑指offer 01. 找出数组中重复的数字

简介: 剑指offer 01. 找出数组中重复的数字

题目描述


给定一个长度为 n 的整数数组 nums,数组中所有的数字都在 0∼n−1 的范围内。


数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。


请找出数组中任意一个重复的数字。


注意:如果某些数字不在 0∼n−1 的范围内,或数组中不包含重复数字,则返回 -1;


数据范围

0≤n≤1000

样例

给定 nums = [2, 3, 1, 0, 2, 5, 3]。
返回 2 或 3。


方法一:哈希表 O(n)


可以利用 c++ 中 unordered_map 哈希表自带的性质,快速在表中查找是否存在当前元素。思路如下:

  1. 从前往后遍历数组元素,并将元素加入哈希表。


  1. 同时每次都判断该元素是否已经在哈希表中出现过,如果出现过就直接返回该值。
class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        unordered_map<int, bool> st;  //用一个哈希表来保存数组中已经出现过的元素
        //判断是否有元素越界
        int n = nums.size() - 1;
        for (auto i : nums)
            if (i<0 || i>n)
                return -1;
        //判断是否有元素重复
        for (auto i : nums) {
            if (st.count(i)) return i;
            st[i] = true;
        }
        return -1;
    }
};



方法二:数组 O(n)

这个方法第一次想可能会有点抽象,我们要做的是每次遍历都将当前位置的元素,放在与它值相等的下标位置,直接上图:


c12f8d267e7c4f5aa47310a0f8d4fcc2.png

f36a7c1d76524d97851a08c8acae55fd.png

741e68b5a223445e9dce85d502c38bf0.png

fa15bf0abf36411587f478609e2e272e.png


class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n=nums.size();
        //判断元素是否越界
        for(auto i: nums)
            if(i<0||i>=n)
                return -1;
        //找到重复元素
        for(int i=0;i<n;i++)
        {
            //将数组中的每个元素放到与其值相等的下标处
            while(nums[nums[i]]!=nums[i])   swap(nums[nums[i]],nums[i]);
            //如果不相等,说明有重复元素占住了那个位置导致无法继续交换
            if(nums[i]!=i)  return nums[i];
        }
        return -1;
    }
};

欢迎大家在评论区交流~

目录
相关文章
|
6月前
|
Java
每日一题《剑指offer》数组篇之数组中重复的数字
每日一题《剑指offer》数组篇之数组中重复的数字
52 0
每日一题《剑指offer》数组篇之数组中重复的数字
【剑指offer】- 数组中重复的数字 -48/67
【剑指offer】- 数组中重复的数字 -48/67
|
6月前
LeetCode(1)-找出数组中重复的数字
LeetCode(1)-找出数组中重复的数字
26 0
|
6月前
剑指Offer 面试题03. 数组中重复的数字
剑指Offer 面试题03. 数组中重复的数字
33 0
剑指offer-1.找出数组中重复的数字
剑指offer-1.找出数组中重复的数字
30 0
剑指offer-2.不修改数组找出重复的数字
剑指offer-2.不修改数组找出重复的数字
46 0
|
C++
剑指Offer - 面试题3:数组中重复的数字
剑指Offer - 面试题3:数组中重复的数字
68 0
|
索引
剑指offer_数组---数组中重复的数字
剑指offer_数组---数组中重复的数字
45 0
剑指offer 02. 不修改数组找出重复的数字
剑指offer 02. 不修改数组找出重复的数字
62 0
|
存储 算法 Java
LeetCode 找出数组中重复的数字
LeetCode 找出数组中重复的数字