Leetcode217——是否存在重复数字

217. 存在重复元素

难度简单969收藏分享切换为英文接收动态反馈

给你一个整数数组 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

题目要找是否有一个只存在 那我们可以让nums数组有序

既然数组都有序了 那么重复的值就紧挨着

那需要怎样寻找呢？

我们可以比较两个紧挨着的值是否相等 如 nums[j]==nums[j+1]

看到这个式子 你想起了那个排序 当然是众所周知的冒泡排序

那我们可以用冒泡排序进行排序

我们不需要再遍历一遍nums数组去判断nums[j]==nums[j+1] 因为那样太浪费时间了

就利用冒泡排序的遍历过程进行判断

bool containsDuplicate(int* nums, int numsSize)
{for(int i = 0;i<numsSize-1;i++){int flag = 0;for(int j = 0;j<numsSize-i-1;j++){if(nums[j]==nums[j+1])//判断部分{return true;}if(nums[j]>nums[j+1]){flag = 1;//改进冒泡排序防止运行时间过长int tmp = nums[j];nums[j] = nums[j+1];nums[j+1] = tmp;}}if(flag == 0)break;}return false;
}

既然提到排序 那有没有想到qsort函数 之前有讲过他的实现和运用

int my_cmp(const void* p1,const void* p2)
{return *(int*)p1-*(int*)p2;
}bool containsDuplicate(int* nums, int numsSize)
{qsort(nums,numsSize,sizeof(int),my_cmp);for(int i = 0;i<numsSize-1;i++){if(nums[i]==nums[i+1]){return true;}}return false;
}

但他的效果没有冒泡排序好

冒泡排序时间复杂度还是挺高的

我本性利用 统计排序做这道题 就是空间复杂度有点高

但是系统判断时间超出限制

看到这个消息之后 我本不想用冒泡排序 因为这个时间复杂度比统计排序还要高

这不是自讨没趣嘛

令我意外的是冒泡排序跑过了

统计排序（没跑过去　思路提供给你）

bool containsDuplicate(int* nums, int numsSize)
{//之所以开辟两个数组 避免将负数转化为正数 再判断开辟数组元素方面做出复杂的判断 去判断这个数是整数还是负数int* tmp = (int*)malloc(sizeof(int)*1000000000);//处理自然数int* arr = (int*)malloc(sizeof(int)*1000000000);//处理负数for(int i = 0;i<numsSize;i++){if(nums[i]>=0){if(tmp[nums[i]]!=1){tmp[nums[i]]=1;}else{return true;}}else{if(arr[nums[i]]!=1){arr[nums[i]]=1;}else{return true;}}}return false;
}

如果有错误指点 我将会及时改正~