【剑指offer】面试题03 - 数组中重复的数字

骑猪看日落 2022-11-01 10:55 144阅读 0赞

### 文章目录 ###

*  面试题3 ：数组中重复的数字
 *   *  解法一：排序后遍历
     *  解法二：哈希表法
     *  解法三：排序

# 面试题3 ：数组中重复的数字 #

> 题目：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
> 
> 链接：[LeetCode][] [牛客网][Link 1]

## 解法一：排序后遍历 ##

> 注意以下几点：
> 
> 1.  将数组中的数字排序
> 2.  从头至尾遍历，判断相邻两个数字是否重复
> 3.  若重复，用一个变量记录下来重复值后break出for循环
> 
> 时间复杂度：O(logN)
> 
> 空间复杂度：O(1)
> 
> 缺点：变动了原数组

class Solution { 
    public:
        int findRepeatNumber(vector<int>& v) { 
            sort(v.begin(), v.end());
            for(int i = 0; i < v.size() - 1; i ++)
                if(v[i] == v[i+1])
                    return v[i];
            return -1;
        }
    };

## 解法二：哈希表法 ##

> 注意以下几点：
> 
> 1.  使用一个辅助数组
> 2.  遍历原数组，将新元素插入辅助数组之前判断辅助数组中是否有该元素
> 3.  若有，则返回该元素
> 
> 时间复杂度：O(N)
> 
> 空间复杂度：O(N)

int findRepeatNumber(vector<int>& v) { 
        set<int> s;
        s.insert(v[0]);
        for(int i = 1; i < v.size(); i++)
            if(s.find(v[i]) == s.end())
                s.insert(v[i]);
        else 
            return v[i];
        return -1;
    }

## 解法三：排序 ##

> 思路：
> 
>  *  数组中的数字都在 0 ~ n-1 之间，一共 n 个数。如果没有重复数字，那么当数组排序之后，数字i将出现在下标为 i 的位置；由于数组中有重复的数字，导致有些位置可能存在多个数字，同时有些位置可能没有数字
>  *  从头到尾扫描每一个数字，当扫描到下标为 i 的数字 m 时：
>     
>      *  如果 m 是等于 i 的，则继续扫描下一个数字；
>      *  如果 m 是不等于 i 的，则将该数字与下标为 m 的数字 n 进行比较：
>         
>          *  如果 m 和 n不相等，则将 m 和 n 进行交换，接下来重复这个比较和交换过程，直到发现 m 与 n 相等的情况
>          *  如果 m 和 n 相等，则找到了重复的数字，将 m 返回即可
>     
>     时间复杂度：O(N)
>     
>     空间复杂度：O(1)
>     
>     缺点：变动了原数组

int findRepeatNumber(vector<int>& v) { 
        for(int i = 0; i < v.size(); i++)
        { 
            while(v[i] != i)
            { 
                if(v[i] == v[v[i]])
                    return v[i];
                swap(v[i],v[v[i]]);
            }
        }
        return -1;
    }

[LeetCode]: https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
[Link 1]: https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&tqId=11203&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey