存在重复

题目链接

传送门

解题思路

方法一

O(n^2)两两比较;

方法二

用STL的map,作Hash映射。若遇到已经在map里的元素,则返回false。时间复杂度O(1);
或者
用STL的set,循环一次insert进set。因为set有去重功能,最后比较下vector和set的大小即可。时间复杂度O(n),空间复杂度O(n);

方法三

排序,然后相邻元素比较。时间复杂度O(nlogn),空间复杂度O(1)。

参考代码

// 使用方法三实现
class Solution {
public:
    int selfSort(vector<int>& nums, int leftIndex, int rightIndex) {
        int element = nums[leftIndex];
        while (leftIndex < rightIndex) {
            // 比element小的值移动到左端
            while (leftIndex < rightIndex && nums[rightIndex] >= element) {
                rightIndex --;
            }
            if (leftIndex < rightIndex) {
                nums[leftIndex] = nums[rightIndex];    
            }
            // 比element大的值移动到右端
            while (leftIndex < rightIndex && nums[leftIndex] <= element) {
                leftIndex ++;
            }
            if (leftIndex < rightIndex) {
                nums[rightIndex] = nums[leftIndex];    
            }
        }
        nums[leftIndex] = element;
        return leftIndex;
    }

    void quickSort(vector<int>& nums, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            int position = selfSort(nums, startIndex, endIndex);
            quickSort(nums, startIndex, position - 1);
            quickSort(nums, position + 1, endIndex);
        }
    }

    bool containsDuplicate(vector<int>& nums) {
        int length = nums.size();
        if (0 == length) {
            return false;
        }
        quickSort(nums, 0, length - 1);

        for (int index = 1; index < length; index ++) {
            if (nums[index - 1] == nums[index]) {
                return true;
            }
        }
        return false;
    }
};

测试样例

  • []
  • [5,-2,0,4,-6]

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2018-2019 惜春令 京ICP备18010644号 网站地图