LeetCode每日一题217: 存在重复元素

今天是一道简单的算法题, 然而我却被LeetCode新提交的测试用例卡住了!

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

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

示例 1:

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

示例 2:

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

示例 3:

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

---

暴力解法

bool containsDuplicate(int* nums, int numsSize) {   
    for(int i=0; i<numsSize; i++){
        for(int j=i+1; j<numsSize; j++){
            if(nums[i] == nums[j])
                return true;
        }
    } 
    return false;  
}

image.png

不出意外的, 这种时间复杂度达到O(n^2)的方法用 Python 实现超时

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if(nums[i] == nums[j]):
                    return True
        return False

---

空间换时间思想

如果这道题限定了数字的范围小于等于数组大小,那么这种方法可以获得接近O(n)的时间复杂度.

判断的方法是构建一个与数组temp[numsSize], 若temp[nums[i]]==0,则此位置为空, 改为1, 若非零则重复.

但是题目中没有限定, 这意味着负数、大于数组大小的数都可以使用,下面是错误示范, 想看正确答案, 跳过这部分.

我想到了用类似散列线性探测法的方法, 用temp[nums[i]%numsSize]是否为0判断有无重复, 为0则赋值为nums[i]/numsSize但是小于数组的的数商为0,于是我在后面+1

但是这样还是不能覆盖所有样例, 因为还有负数的情况, 于是我有用了一个flag变量与结果相乘, 再进行判断.

然而还是无法覆盖...这次已经到达第17个样例, 什么问题呢?就是当你的商为-1的时候, +1会变成0,这样又冲突了....

如果你有兴趣, 可以试试改这段代码, 让它通过测试, 估计速度不会特别差.

bool containsDuplicate(int* nums, int numsSize) {
    int *temp;
    int flag = 1;
    // 申请标记数组,对应位置为除数值则表示已有
    temp = (int *)malloc(sizeof(int)*(numsSize));
    for(int i=0; i<numsSize; i++){
        if(nums[i]<0)
        {
            nums[i]= -nums[i];
            flag = -1;
        }
        if(temp[nums[i]%numsSize]==0){
            // +1让小于numsSize的数对应位置的值大于0
            temp[nums[i]%numsSize] = flag*(nums[i]/numsSize+1);
        }
        else if(temp[nums[i]%numsSize]!=0 && 
                 temp[nums[i]%numsSize] == (nums[i]/numsSize+1))
        {
            return true;
        }       
        else{
        }
    }
    return false;
}

---

正解

哈希是最快的算法, 其次是用快速排序, 然后遍历.

Python在这里显示出极强的简洁性, 用集合自带的哈希算法
只需一条语句就可以实现

def containsDuplicate(self, nums):
        return len(set(nums))!=len(nums)

下面这个解法是网友给出的, 结构是双层嵌套, 但是运行结果居然才8ms, 很神奇. 不知道是不是测试例子不够极端.

bool containsDuplicate(int* nums, int numsSize) {
    for(int i=0; i<numsSize; i++){
        for(int j = i-1; j>=0; j--){
            if(nums[i] > nums[j])
                break;
            else if(nums[i] == nums[j])
                return true;
        }
    }
    return false;
}

结果