剑指offer.03. 数组中重复的数字

题目描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

利用哈希表

class Solution { public: int findRepeatNumber(vector<int>& nums) { unordered_set<int> nSet; for(int i : nums) { if(nSet.count(i) != 0) return i; // 假如hashset中已经有i了，说明重复了，返回i else nSet.insert(i); } return -1; } }; 作者：superkakayong 链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/zi-jie-ti-ku-jian-3-jian-dan-shu-zu-zhong-zhong-fu/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

利用unordered_set的count函数，看哈希表中是否已经存在了某个数字，已经存在了，说明重复，直接输出；如果不存在，就利用insert函数把这个数字插入到哈希表中。 时间复杂度和空间复杂度都是O(N)。

布尔数组判重

注意到条件中有所有数字的范围是0~n-1。布尔数组判重就是利用这个条件。 建立一个布尔数组bool flag[nums.size( )]，然后对于每一个i，查询flag[nums[i]]，如果是false，说明nums[i]还没有出现过，然后将flag[nums[i]]重置为true；如果flag[nums[i]]是true，说明之前nums[i]已经出现过了，直接输出nums[i]。 关键就是nums[i]$\le n-1$，数组不会越界。

class Solution { public: int findRepeatNumber(vector<int>& nums) { bool flag[nums.size()]; memset(flag, false, sizeof(flag)); for(int i = 0; i < nums.size(); i++) if(flag[nums[i]]) return nums[i]; else flag[nums[i]] = true; return -1; } }; 作者：lhh2001-2 链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/bu-er-shu-zu-pan-zhong-by-lhh2001-2/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。