力扣-剑指 Offer 03. 数组中重复的数字（C++）- 哈希+非哈希

Dear 丶 2022-09-07 14:38 287阅读 0赞

题目链接：[https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/][https_leetcode-cn.com_problems_shu-zu-zhong-zhong-fu-de-shu-zi-lcof]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
解法一：哈希

class Solution {
        
    public:
        int findRepeatNumber(vector<int>& nums) {
        
            unordered_set<int> uset;
    
            for(auto num:nums)
            if(uset.count(num)!=0) return num;
            else uset.insert(num);
    
            return -1;
        }
    };

解法二：非哈希

class Solution {
        
    public:
        int findRepeatNumber(vector<int>& nums) {
        
        //思路：把每个数字i都放在下标为i的位置上，如果遇到正准备交换时，位置上已有元素，那么这个数就是重复的数
            for (int i=0;i<nums.size();) {
        
                if (i==nums[i]) ++i;
                else if (nums[i] == nums[nums[i]]) return nums[i];
                else {
        
                    swap(nums[i],nums[nums[i]]);
                }
            }
            return -1;
        }
    };

[https_leetcode-cn.com_problems_shu-zu-zhong-zhong-fu-de-shu-zi-lcof]: https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/17a1d5efdae94cd1a03f5cfa132824ed.png

发表评论取消回复

表情：

评论列表（有 0 条评论，287人围观）

还没有评论，来说两句吧...

相关阅读

相关力扣-217题存在重复元素（C++）- 哈希

题目链接：[https://leetcode-cn.com/problems/contains-duplicate/][https_leetcode-cn.com_proble

灰太狼/ 2023年01月23日 11:47/ 0 赞/ 22 阅读

相关力扣-202题（Java）-哈希

题目链接：[https://leetcode-cn.com/problems/happy-number/][https_leetcode-cn.com_problems_hap

╰半夏微凉°/ 2023年01月20日 11:57/ 0 赞/ 148 阅读

相关力扣-387题（Java）-哈希

题目链接：[https://leetcode-cn.com/problems/first-unique-character-in-a-string/][https_leetco

r囧r小猫/ 2023年01月19日 04:36/ 0 赞/ 145 阅读

相关寻找重复数287-力扣（数组+【快排|哈希|二分】+c）

题目描述给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有一个重

傷城~/ 2023年01月19日 03:28/ 0 赞/ 20 阅读

相关力扣-961题（Java）-哈希

题目链接：[https://leetcode-cn.com/problems/n-repeated-element-in-size-2n-array/][https_leetc

爱被打了一巴掌/ 2023年01月18日 14:24/ 0 赞/ 17 阅读

相关力扣-217题（Java）-哈希

题目链接：[https://leetcode-cn.com/problems/contains-duplicate/][https_leetcode-cn.com_proble

朴灿烈づ我的快乐病毒、/ 2023年01月18日 09:28/ 0 赞/ 197 阅读

相关力扣-剑指 Offer 50. 第一个只出现一次的字符（C++）- 数组作哈希

题目链接：[https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/][https

迷南。/ 2022年09月09日 04:59/ 0 赞/ 99 阅读

相关力扣-202题快乐数（C++）- 哈希

题目链接：[https://leetcode-cn.com/problems/happy-number/][https_leetcode-cn.com_problems_hap

电玩女神/ 2022年09月07日 14:59/ 0 赞/ 216 阅读

相关力扣-剑指 Offer 03. 数组中重复的数字（C++）- 哈希+非哈希

题目链接：[https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/][https_leet

Dear 丶/ 2022年09月07日 14:38/ 0 赞/ 288 阅读

相关力扣-383题赎金信（C++）- string + 数组哈希

题目链接：[https://leetcode-cn.com/problems/ransom-note/][https_leetcode-cn.com_problems_rans

妖狐艹你老母/ 2022年08月30日 05:25/ 0 赞/ 173 阅读