217.Contains Duplicate I

August 16, 2016

217.Contains Duplicate I

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

判断数组中是否有重复元素系列中的第一题,最容易想到的办法是双指针法,也就是双重循环,O(n^2)的时间复杂度。不过通过排序,可以将时间复杂度降低到O(n),代码如下:

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if(nums.size()==0||nums.size()==1)
            return false;
        sort(nums.begin(),nums.end());
        int i=0;
        for(i;i<nums.size();i++){
            if(nums[i]==nums[i+1])
                return true;
        }
        return false;
    }
};

这道题也可以用hash_table来完成,不过还是需要一次循环,意义不大。

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017