广东手机微信网站制作,徐州网站建设解决方案,哪个网站可以做puzzle,网站左侧悬浮代码题目描述#xff1a;
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 #xff0c;返回 true #xff1b;如果数组中每个元素互不相同#xff0c;返回 false 。 示例 1#xff1a;
输入#xff1a;nums [1,2,3,1]
输出#xff1a;true
示例 2#xff1a;…题目描述
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 返回 true 如果数组中每个元素互不相同返回 false 。 示例 1
输入nums [1,2,3,1]
输出true
示例 2
输入nums [1,2,3,4]
输出false
示例 3
输入nums [1,1,1,3,3,4,3,2,4,2]
输出true 提示
1 nums.length 105-109 nums[i] 109
算法一排序法
思路
将所有元素进行排序对相邻元素比较是否相同找出重复元素
代码实现
# includestdlib.hint cmp(const void* _a, const void* _b) {int a *(int*)_a, b *(int*)_b;return a - b;
}bool containsDuplicate(int* nums, int numsSize) {//排序qsort(nums, numsSize, sizeof(int), cmp);//相同的数会相邻 所以检查相邻元素是否相同即可for (int i 0; i numsSize - 1; i) {if (nums[i] nums[i 1]) {return true;}}return false;
}
算法二hash表
思路
创建hash表利用取余来降低数据大小具体实现见注释
代码实现
bool containsDuplicate(int* nums, int numsSize){if(numsSize2)//边界情况判断return false;int Hasharr[numsSize];int count 0;int reminder 0;//初始化for(int i0;inumsSize;i){Hasharr[i] 0;}for(int i0;inumsSize;i){//单独对0讨论--防止与可被整除的数混淆if(nums[i] 0){count;if(count 2)return true;continue;}// 4 100 1000 -50 1000reminder nums[i]%numsSize;if(reminder0)remindernumsSize;while(true){if(Hasharr[reminder]0){//未存放--存入新数据--下一轮Hasharr[reminder] nums[i];break;}//比对数据else if(Hasharr[reminder] nums[i]){return true;}//不同--移位--重复判断是否一存放else{reminder;if(remindernumsSize)reminder-numsSize;}}}return false;
}
