217.存在重复元素

发表于 | 分类于
字数统计: 410 | 阅读时长 ≈ 2

一、题目描述

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:

1
2
输入: [1,2,3,1]
输出: true

示例 2:

1
2
输入: [1,2,3,4]
输出: false

示例 3:

1
2
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

二、题解

1. 算法描述

  • 暴力法：两个for循环嵌套遍历
  • 使用qsort()排序，再逐位检查

2. 个人分析

  • 暴力法超时
  • qsort()最坏复杂度：O(nlogn)

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}
bool containsDuplicate(int *nums, int numsSize)
{
    if (numsSize < 2)
        return false;
    int sizeOfElem = sizeof(int);
    qsort(nums, numsSize, sizeOfElem, compare);
    int i;
    for (i = 0; i < numsSize - 1; i++)
    {
        if (nums[i] == nums[i + 1])
            return true;
    }
    return false;
}

三、PS：

  • 暴力法超时

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    bool containsDuplicate(int *nums, int numsSize)
    {
        if (numsSize == 1)
            return false;
        int i, j;
        for (i = 0; i < numsSize; i++)
        {
            for (j = i + 1; j < numsSize; j++)
            {
                if (nums[i] == nums[j])
                {
                    return true;
                }
            }
        }
        return false;
    }

  • qsort()快速排序：

    void qsort(void *_Base, size_t _NumOfElements, size_t _SizeOfElements, int (*_PtFuncCompare)(const void *, const void *))

    • _Base：待排序的数组
    • _NumOfElements：数组中元素的个数
    • _SizeOfElements：数组中元素的大小
    • (_PtFuncCompare)(const void , const void *))：比较指针

  • qsort()函数实例：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    int compare1(const void *a, const void *b)
    {	//升序
        return (*(int *)a - *(int *)b);
    }
    int compare2(const void *a, const void *b)
    {	//降序
        return (*(int *)b - *(int *)a);
    }
    int main()
    {
        int array[] = {4, 5, 3, 6, 2, 5, 1};
        int numsOfArray = sizeof(array) / sizeof(array[0]);
        int sizeOfElem = sizeof(array[0]);
        qsort(array, numsOfArray, sizeOfElem, compare1);
        int i;
        for (i = 0; i < numsOfArray; i++)
        {
            printf("%d", array[i]);
        }
    }