［LeetCode］Contains Duplicate-白红宇

［LeetCode］Contains Duplicate

阅读量：2236 次

发布时间：2019-05-09

本文共 2752 字，大约阅读时间需要 9 分钟。

方法1:

解题思路：

1，先排序；

2，再一次遍历，比较相邻两个数，相同则返回true；

排序用快排：

1，前条件：first, last，flag

2，不变式：从last开始找，找到比flag小的数字，放在first那里，然后从first下一位开始找，找到比flag大的，放到last那里；

3，结束条件：first == last

4，临界条件：nums为空或者长度为1

// 快排超时了！

// 因为快排在原数据是有序的或者逆序的时候，退化为O(n2)

class Solution {public:    bool containsDuplicate(vector
   
    & nums) {        if (nums.size() <= 1)            return false;        Sort(nums);        for (int i = 1; i < nums.size(); ++i){            if (nums[i] == nums[i-1])                return true;        }        return false;    }    void Sort(vector
    
     & nums){        if (nums.size() <= 1)            return;        int len = nums.size();        quickSort(nums, 0, len-1);    }    void quickSort(vector
     
      & nums, int begin, int end){        if (begin >= end)            return;        int first = begin;        int last = end;        int flag = nums[first];        while (first < last){            while(nums[last] >= flag && last > first){                last--;            }            if (last > first){                nums[first++] = nums[last];            }            while(nums[first] <= flag && first < last){                first++;            }            if (first < last){                nums[last--] = nums[first];            }        }        nums[first] = flag;        int mid = first;        quickSort(nums, begin, mid-1);        quickSort(nums, mid+1, end);    }};

// 快排Java实现

private void quickSort(int[] nums, int start, int end){        if (end - start < 1) return ;        int p = start;        int q = end;        int tmp = nums[start];                while(p < q){            while(p < q && nums[q] >= tmp) q--;            if (p < q) nums[p++] = nums[q];                        while( p < q && nums[p] <= tmp) p++;            if (p < q) nums[q--] = nums[p];        }        nums[p] = tmp;        quickSort(nums, start, p-1);        quickSort(nums, p+1, end);    }

方法二：

// 但凡时间不够用，那就只能空间换时间了

这时候想到STL里面的set集合类型，其元素不可以重复，于是可以利用set的insert操作的返回值，来判断是否duplicate。

set实现了红黑书的er

set.insert()返回pair，利用其second判断是否插入成功

// 因为利用了牛逼的数据结构，代码变的如此简洁。我知道STL有quickSort方法，在上面，我就是想自己写一遍，不喜勿喷！

class Solution {public:    bool containsDuplicate(vector
   
    & nums) {        if (nums.size() <= 1)            return false;        set
    
      s;        for (int i = 0; i < nums.size(); ++i){            if (s.insert(nums[i]).second)                continue;            return true;        }        return false;    }};

set集合容器：实现了红黑树的平衡二叉检索树的数据结构，插入元素时，它会自动调整二叉树的排列，把元素放到适当的位置，以保证每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值；另外，还得保证根节点左子树的高度与右子树高度相等。

平衡二叉检索树使用中序遍历算法，检索效率高于vector、deque和list等容器，另外使用中序遍历可将键值按照从小到大遍历出来。

构造set集合主要目的是为了快速检索，不可直接去修改键值。

方法三：

利用map这个数据结构

每从nums中取一个数，先在map中搜索一遍，不存在就把这个数放在map中，作为key，value＝1。否则发现duplicate。

转载地址：http://ujpbb.baihongyu.com/

你可能感兴趣的文章