硬件工程师都没人干了,西安优化seo托管,阿里云做网站买什么软件,app网站区别面试题3 数组中重复的数字
题 目 #xff1a;找出数组中重复的数字。在一个长度为n的数组里的所有数字都在0 ~ n-1的范围内。数组中某些数字是重复的#xff0c;但不知道有几个数字重复了#xff0c;也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如找出数组中重复的数字。在一个长度为n的数组里的所有数字都在0 ~ n-1的范围内。数组中某些数字是重复的但不知道有几个数字重复了也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如如果输入长度为7 的数组2,3, 1,0, 2, 5, 3 , 那么对应的输出是重复的数字2 或者3。先把输入的数组排序。从排序的数组中找出重复的数字是一件很容易的事情只需要从头到尾扫描排序后的数组就可以了。排序一个长度为n的数组需要O(nlogn)的时间还可以利用哈希表来解决这个问题。从头到尾按顺序扫描数组的每个数字每扫描到一个数字的时候都可以用0(1)的时间来判断哈希表里是否已经包含了该数字。如果哈希表里还没有这个数字就把它加入哈希表。如果哈希表里已经存在该数字就找到一个重复的数字。这个算法的时间复杂度是0(n)但它提高时间效率是以一个大小为o(n)的哈希表为代价的。我们再看看有没有空间复杂度是0(1)的算法。如果这个数组中没有重复的数字那么当数组排序之后数字i将出现在下标为 i 的位置。由于数组中有重复的数字有些位置可能存在多个数字同时有些位置可能没有数字。现在让我们重排这个数组。从头到尾依次扫描这个数组中的每个数字。当扫描到下标为i的数字时首先比较这个数字(用m表示)是不是等于i. 如果是则接着扫描下一个数字如果不是则再拿它和第 m 个数字进行比较。如果它和第m个数字相等就找到了一个重复的数字(该数字在下标为i和m 的位置都出现了)如果它和第m个数字不相等就把第i个数 字和第m个数字交换把m 放到属于它的位置。接下来再重复这个比较、 交换的过程直到我们发现一个重复的数字例子数组{2,3,1,0,2,5,3};数组的第0个数字(从0开始计数)是2与他的下标不匹配因此将a[0]元素指定的坐标2互换换完之后的结果是{1,3,2,0,2,5,3};这个时候0号元素是1仍然和小标不匹配继续更换更换之后的结果是{3,1,2,0,2,5,3};接下来继续交换第0号元素和第3号元素{0,1,2,3,2,5,3};0号元素、1号元素、2号元素、3号元素均匹配当4号元素对应的数值是2和2号元素重复因此找到了一个重复的数字
class Solution {
public:int findRepeatNumber(vectorint nums) {int length nums.size();/* if (length 0){return -1;}for (int i 0; i length; i) {if (nums[i] 0 || nums[i] length){return false;}}*/for (int i 0; i length; i) {while (nums[i] ! i){if (nums[i] nums[nums[i]]){return nums[i];} else{int temp nums[i];nums[i] nums[temp];nums[temp] temp;}}}return -1;}
};Leetcode对应的题目地址
第二种解法
使用map第一次遍历元素key是元素的本身数值value是元素出现的次数存储所有的元素和出现次数的相关信息第二次遍历元素查找元素出现的次数大于等于2的返回对应的元素 int findRepeatNumber_3(std::vectorint nums) {std::mapint,int map{};int length nums.size();for (int i 0; i length; i) {map[nums[i]];}for (auto i map.cbegin(); i ! map.cend(); i) {if (i-second 2){return i-first;}}return -1;}第三种解法
使用无需map将元素加入map的时候就要判定是不是之前已经存在了此元素如果存在此元素将其返回 int findRepeatNumber_2(std::vectorint nums) {std::unordered_mapint,int map{};int length nums.size();for (int i 0; i length; i) {if (map.find(nums[i]) ! map.end()){return nums[i];} else{map[nums[i]];}}return -1;}第四种解法
将元素按照次序进行排序然后判断相邻元素是否相等如果相等则将其返回
