重复元素存在判断

ynnh

给你一个整数数组 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[j] == nums[i])
        {
            return true;
        }
        else
        {
            j++;
        }
        if (j == numsSize)
        {
            i++;
            j = i + 1;
        }
    }
    return false;
}
这段代码哪里出错了吗

isdkz

这段代码的算法思路是双指针，即用 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[i-1]) {
            return true;
        }
    }
    return false;
}

int cmp(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

这段代码的时间复杂度为 O(nlogn)，因为排序的时间复杂度是 O(nlogn)。