changed 2 years ago  
Published Linked with GitHub

Leetcode刷題學習筆記–Set/Multiset

Introduction

ref : Difference Between set, multiset, unordered_set, unordered_multiset in C++

排序 允許重複資料 用途
set
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
排序不重複資料
unordered_set 檢查資料單一性
當成hash table使用
multiset
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
排序重複資料
unordered_multiset
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
  • set/multiset只能存放一個資料，不像map可以存key-value pair。
  • 數字放入set會依小到大排序，字串放入set會依字典序排序。

Time Complexity

ref : Data Structures: MULTI_SET vs SET vs UNORDERED_SET

Container insert() erase() find() Implement
set \(O(logN)\) \(O(logN)\) \(O(logN)\) Binary Search Tree
unordered_set \(O(1)\) \(O(1)\) \(O(1)\) Hash Table
multiset \(O(logN)\) \(O(logN)\) \(O(logN)\) Red Black Tree
unordered_multiset \(O(1)\) \(O(1)\) \(O(1)\) Hash Table

Code snippet

檢查資料是否重複

把每筆資料轉換成單一的識別碼，從而檢查是否重複。可以使用set。





vector<int> nums;
unordered_set<int> s(nums.begin(), nums.end());
// check if num has alreay existed in set
if(s.count(num)) {...}

只能insert和erase不能修改資料





unordered_set<int> s;
s.insert(1);
s.insert(2);
s.erase(1);
  • multiset/unordered_multiset 的資料刪除
    因為multiset和unordered_multiset可以允許重複的資料，
    使用erase或刪除相同的資料，所以必須使用find。


multiset<int> ms;
ms.erase(ms.find(num));

如果是插入到set或是multiset，可以知道插入的位置。

視情況如果想知道insert的位置。





set<int> s;
int nums = 5;
auto it = s.insert(nums); // get the iterator of inserted number
int idx = it - s.begin();

Traversal the set

使用iterator來存取所有的item，或是使用for loop來存取所有的資料。
ref : Different ways to iterate over a set in C++




















set<int> s;
// iterator為指向set中的element，可視為pointer，必須使用*來取值。
for(auto it = s.begin(); it != s.end(); ++it)
    cout << *it << endl; 

// for loop 直接就會拿到element的reference
for(auto& n : s)
    cout << n << endl;

// 必須使用const來定義輸入argument，因為set內的element也是const，
// 所以只能刪除不能修改。
// (start iterator, end iterator, funcion pointer)
auto print = [&](const int& x) {
    cout << x << endl;    
};
for_each(s.begin(), s.end(), print);
for_each(s,begin(), s.end(), [&](const int& x){
   cout << x << endl; 
});

改變Set排列順序

  • 預設Set排列，integer為從小到大，string為字典序排列。
  • 但是有些情況想要有integer從大到小的排列。
  1. 使用iterator



for(auto it = s.rbegin(); it != r.end(); ++it) {
    cout << *it << endl;
}
  1. 使用compare


set<int, less<int>> s; // 從小到大
set<int, greater<int>> s; //從大到小
  1. 反轉key




vector<int> nums;
set<int> s;
for(auto& n : nums)
    s.insert(-1 * n);

Sets of pairs in C++

ref : Sets of pairs in C++
在Set中存放pairs。則會先依pairs first element排序，如果first element一樣就會用second element排序。

Custom Comparator

ref : Using custom std::set comparator

  • Modern C++11 Solution




auto cmp = [](int a, int b) {
    return a < b; // 從小到大
};
set<int, decltype(cmp)> s(cmp);
  • function pointer




bool cmp(int a, int b) {
    return a < b;
}
set<int, decltype(&cmp)> s(&cmp);

36. Valid Sudoku(Medium)

找出行,列，每個block是否有數字重複。


























class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<string> s;
        string t1, t2, t3;
        for(int i = 0; i < 9; ++i) {
            for(int j = 0; j < 9; ++j) {
                if(board[i][j]=='.') continue;
                t1 = to_string(i) + "r" + board[i][j];
                t2 = to_string(j) + "c" + board[i][j];
                t3 = to_string(i / 3) + to_string(j / 3) 
                            + "e" + board[i][j];
                if(s.count(t1) || s.count(t2) || s.count(t3)) 
                   return false;
                else {
                    s.insert(t1);
                    s.insert(t2);
                    s.insert(t3);
                }
            }
        }
        
        return true;
    }
};

929. Unique Email Addresses(Easy)

找出不同的email address，判斷規則參考題目。

使用unordered_set來過濾是否有重複的email address。unordered_set<string> valid_mails;
把email分成local name和domain name。對localname進行處理。把"+"以後的字串都刪除掉，然後把"."都拿掉。

完整程式碼如下:














int numUniqueEmails(vector<string>& emails) {
    unordered_set<string> valid_mails;
    for(auto& mail : emails) {
        int pos = mail.find("@");
        string localname = mail.substr(0, pos);
        string domainname = mail.substr(pos + 1);
        int p = localname.find("+");
        string newname = localname.substr(0, p);
        newname.erase(std::remove(newname.begin(), newname.end(), '.'), newname.end());
        valid_mails.insert(newname + "@" + domainname);
    }      
    return valid_mails.size();
}

220. Contains Duplicate III

給你一個vector<int> nums, 找出index差小於等於k，且數字差小於等於t。
\(abs(num[i] - nums[j]) <= t\) 且 \(abs(i - j) <= k\)。

  1. 因為限制index差在k之內，所以使用slinding window，新增一個數nums[i]就刪除nums[i - k - 1]
  2. 使用multiset來記錄數字，因為數字可能重複。
  3. 因為題目是要差值小於t，所以insert之後的數字只需要跟前後去比較。
  4. 刪除的時候必須使用 s.earse(s.find(val)); 避免刪除全部相同的key。，因為可能會遇到windows中好幾個相同的數值。

















bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
    multiset<long> s;
    for(int i = 0; i < nums.size(); ++i) {
        // 使用find之後再erase避免刪除重複的key
        if(i - k - 1 >= 0) 
            s.erase(s.find(nums[i - k - 1])); // O(logK + logK)
        // insert之後取得在multiset之中的位置。
        auto it = s.insert(nums[i]); // O(logK)
        if(it != s.begin() && it - *prev(it) <= t) return true;
        if(next(it) != s.end() && *next(it) - *it <= t) return true;
    
        // time  : O(N*3*logK) = O(NlogK), 
        //         K : size of slinding window
        // space : O(K)
    }
    return false;
}
tags: leetcode 刷題
Select a repo