Contains Duplicate Emma C++ Note

Programming Language: C++

Back to Leetcode Blind 75 Practice Note

Leetcode: Contains Duplicate

• 一開始寫的code，顯示time limit exceeded，BigO是O(n^2)
  超過Leetcode可接受的效能了，並不代表答案錯誤，是效能太差
  參考這篇文
  

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;
    }
};

• 常見的時間複雜度
  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 排序用法與範例完整介紹