重复元素存在判断
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。bool containsDuplicate(int* nums, int numsSize){
if (numsSize < 2)
{
return false;
}
int flag = 0;
int i = 0;
int j = 1;
while (i < numsSize - 1)
{
if (nums == nums)
{
return true;
}
else
{
j++;
}
if (j == numsSize)
{
i++;
j = i + 1;
}
}
return false;
}
这段代码哪里出错了吗 这段代码的算法思路是双指针，即用 i 指针指向当前元素，j 指针指向下一个元素，如果发现相同的元素就返回 true，否则 j 指针向后移动。如果 j 指针到达数组末尾，则 i 指针向后移动一位，j 指针指向 i+1 位置。这个思路本质上是暴力搜索，时间复杂度是 O(n^2)。
这段代码的问题在于没有考虑到数组中元素可能为负数的情况，因此需要在比较元素是否相同之前先将数组排序，否则会出现错误的结果。
正确的代码应该是这样的：
bool containsDuplicate(int* nums, int numsSize){
if (numsSize < 2) {
return false;
}
// 先将数组排序
qsort(nums, numsSize, sizeof(int), cmp);
for (int i = 1; i < numsSize; i++) {
if (nums[ i] == nums) {
return true;
}
}
return false;
}
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
这段代码的时间复杂度为 O(nlogn)，因为排序的时间复杂度是 O(nlogn)。
页:
[1]