# Contains Duplicate Emma C++ Note
## Programming Language: C++
### Back to [Leetcode Blind 75 Practice Note](/xh5b5HXPTHGz_jwwymNKlw)
[Leetcode: Contains Duplicate](https://leetcode.com/problems/contains-duplicate/description/)

* 一開始寫的code，顯示time limit exceeded，BigO是O(n^2)
超過Leetcode可接受的效能了，並不代表答案錯誤，是效能太差
參考[這篇文](https://medium.com/@ma87102419/%E7%A8%8B%E5%BC%8F%E5%AF%AB%E5%A5%BD%E8%B7%91%E4%B8%8D%E5%AE%8C-time-limit-exceeded%E6%80%8E%E9%BA%BC%E8%BE%A6-9b5951f8a164)

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {

        int allNumCount = nums.size();
        int sameNumCount = 0;
        bool boolRepeatNum = false;

        for ( int i = 0; i < allNumCount; i++ )
        {
            for ( int j = i+1; j < allNumCount; )
            {
                if (nums[i] == nums[j])
                {
                    boolRepeatNum = true;
                    return boolRepeatNum;
                }
            }
        }
        return boolRepeatNum;
    }
};

* [常見的時間複雜度](https://medium.com/@ma87102419/%E7%A8%8B%E5%BC%8F%E5%AF%AB%E5%A5%BD%E8%B7%91%E4%B8%8D%E5%AE%8C-time-limit-exceeded%E6%80%8E%E9%BA%BC%E8%BE%A6-9b5951f8a164)
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(3^n) < O(n!)
我的答案是O(n²)，太久了，要想辦法提升效率。
圖片來源：http://robot39.blogspot.com/2013/09/computing-power-and-time-complexity.html

* 改成以下答案就可以被接受了

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {

        sort(nums.begin(), nums.end()); // 先由小到大排序
        int allNumCount = nums.size();

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

* 這次學習到的C++新用法：sort()
詳細教學可以參考這篇：[C++ std::sort 排序用法與範例完整介紹](https://shengyu7697.github.io/std-sort/)