題目出處

難度

Easy

題目分類

Array, Hash Table, Sorting

個人範例程式碼

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        // unordered_set set
        // Hash table | RB-tree
        // (unordered) | (ordered)
        // insert and search fast O(1) | search fast only when data less
        // memory use more | memory use less
        //
        // set: ordered, print as ascend, need know n-1...
        // unordered: no-sort needed, single lookup, only insert, delete, search
        set<int> s(nums.begin(), nums.end());
        // for(auto it = s.begin(); it != s.end(); it++)
        //     cout << *it << endl;
        return nums.size() != s.size();
    }
};

說明

這題考的東西很簡單，就是找有沒有重複的東西，
「找重複」非常適合使用 set 來做，我們只需要比較 set 之後的大小是否等於原長度即可。

C++ set 用法整理

set, unordered_set 的差別

說到 C++ 的 set，我們可以先來比較 set, unordered_set 的差別，

	set	unordered_set
實現方式	RB-tree	Hash table
順序	ordered	unordered
速度	search fast only when data less	insert and search fast O(1)
空間使用	memory use less	memory use more
使用場合	ordered/ print as ascend(descend)/ need know realtion of n-1, n-2...	no-sort needed/ single lookup/ only insert, delete, search

vector 轉 set, vector to set

剛好此題目有需要 vector 轉 set，
我們這邊示範一下如何轉換這樣的資料結構。

而轉換的過程中，重複的部分會因為 set 的特性自然地消失，
因此在這題目中我們能夠自然地知道有沒有重複的內容。

vector<int> v;
set<int> s(v.begin(), v.end());
for(auto it = s.begin(); it != s.end(); it++)
    cout << *it << endl;

如何印 set, how to print set

如果我們使用一般的 for 迴圈，因為 set 不具有「順序性」
(這裡指的不是有沒有 unordered 的問題，而是資料結構本身)
我們沒有辦法用 index 的方式去呼叫，類似 set[0], set[1]…

因此我們會需要宣告一個 iterator 幫助我們遍歷這個資料結構!
以下示範剛好結合 vector 轉換 set 的內容：

vector<int> v;
set<int> s(v.begin(), v.end());
for(auto it = s.begin(); it != s.end(); it++)
    cout << *it << endl;

補充一個類似的 map, unordered_map

map 就類似 python 中的 dict (抱歉作者比較熟 python XDD)，
總之就是有「key-value」 pair 的資料結構

	map	unordered_map
實現方式	RB-tree	Hash table
順序	ordered	unordered
速度	慢 (但效率穩定)	快
空間使用	節省 memory	使用較多 memory
使用場合	元素自動排序	元素不需要排序/ only insert, delete, search/ 不需要擔心 memory 使用

【Leetcode】C++ - [217] Contains Duplicate 個人解法筆記 (內含範例程式碼) 內含 C++ set, unordered_set 用法整理