leetcode287寻找重复数

一、问题描述二、解题思路解法一排序搜索首先对nums向量进行一个排序重复出现的数字会挨在一起进行搜索即可。解法二哈希统计频率使用哈希表来统计每个数字出现的次数如果某一数字出现次数超过1次返回即可。解法三快慢双指针由于本题的数字的范围为[0,n]数组的下标为[0,n]经过分析可以得知本题实质上是在找环的入口可以使用快慢双指针来解决(1)首先初始化slow指针为nums[0]fast指针为nums[nums[0]]slow指针每次走一步fast指针每次走两步直至slowfast(2)再定义一个新指针ptr初始化为nums[0]ptr和fast每次走一步直至二者相遇返回此时的ptr即为所求。三、代码实现解法一排序搜索class Solution { public: int findDuplicate(vectorint nums) { //排序搜索 sort(nums.begin(),nums.end()); for(int i0;i!nums.size()-1;i) if(nums[i]nums[i1]) return nums[i]; return -1; } };解法二哈希统计频率class Solution { public: int findDuplicate(vectorint nums) { //哈希表 unordered_mapint,int hash; for(auto x:nums){ hash[x]; if(hash[x]1) return x; } return -1; } };解法三快慢双指针class Solution { public: int findDuplicate(vectorint nums) { // 快慢双指针 int slow nums[0]; int fast nums[nums[0]]; // 第一阶段找到环中的相遇点 while (slow ! fast) { slow nums[slow]; fast nums[nums[fast]]; } // 第二阶段找到环的入口重复的数字 int ptr 0; while (ptr ! slow) { ptr nums[ptr]; slow nums[slow]; } return ptr; } };