# Hash Table
###### tags: `LeetCode筆記`
* It is easy to use a hash function with the help of standard template libraries.
* Most common languages such as C++, Java and Python support both hash set and hash map.
## :memo: 一、基本介紹
### Hash Function : y = x % 5
* Ideally, a perfect hash function will be a one-one mapping between the key and the bucket.
* However in most cases, a hash function is not perfect and it is a **tradeoff** between **the amount of buckets** and **the capacity of a bucket**.
### Collision Resolution
* the maximum number of keys is **N**
* If N is **constant and small**, we can simply use an **array** to store keys in the same bucket.
* If N is **variable or large**, we might need to use **height-balanced binary search tree** instead.
### Two basic operations in a hash table
* Insert
* search
When we remove an element, we will first search the element and then remove the element from the corresponding position if the element exists.
### HashSet
宣告一個bucket陣列去記錄每一個key是否存在於hashset，元素=1為存在,元素=0為不存在。
```
int arr[bucket_size];
memset(arr, 0, sizeof(arr));
```
### HashMap
宣告一個bucket陣列去記錄每一個key的value，陣列的index為key,陣列的元素為value。
```
arr[key] = value;
```
## :memo: 二、基本架構 C
### link list當bucket
```
typedef struct Table {
int value;
struct Table *next;
}table;
```
### link list陣列當dictionary
```
#define HASHSIZE 100
table **list = (table **) malloc(HASHSIZE * sizeof(table*));
for (int i = 0; i < HASHSIZE; i++)
{
list[i] = NULL;
}
```
### hash function
```
#define MAXN 1000000000
int hash(int value)
{
return ((value + MAXN) /97 + 4479) % HASHSIZE;
}
```
### insert() for迴圈寫法
```
unsigned hashVal = (unsigned) hash(val);
struct table *np = malloc(sizeof(struct table));
np->val = val;
np->idx = idx;
//此寫法是將新的node放在開頭
np->next = dict[hashVal];
dict[hashVal] = np;
```
### search() for迴圈寫法
```
unsigned hashVal = (unsigned) hash(val);
for (struct table *np = dict[hashVal]; np; np = np->next)
{
if (np->val == val)
{
return np;
}
}
return NULL;
```
### free()
```
void listFree(table *list)
{
if (list == NULL)
{
return;
}
else
{
listFree(list->next);
free(list);
}
}
```
## :memo: 三、基本知識
### ascii character 有256個
### 宣告二維int指標
```
returnColumnSizes[0] = (int*) malloc(sizeof(int) * (*returnSize));
//*returnColumnSizes = (int*) malloc(sizeof(int) * (*returnSize));
for (int i = 0; i < *returnSize; i++)
{
returnColumnSizes[0][i] = colsize[i];
//*(returnColumnSizes[0] + i) = colsize[i];
}
```
### 宣告三維char指標
```
char*** ret = (char***) malloc(sizeof(char**) * (*returnSize));
for (int i = 0; i < *returnSize; i++)
{
ret[i] = (char**) malloc(sizeof(char*) * returnColumnSizes[0][i]);
//*(ret + i) = (char**) malloc(sizeof(char*) * returnColumnSizes[0][i]);
}
p = hashmap->head;
struct node* e = p->head;
for (int i = 0; i < *returnSize && p != NULL; i++)
{
e = p->head;
//printf("%d ",returnColumnSizes[0][i]);
for (int j = 0; j < returnColumnSizes[0][i] && e != NULL; j++)
{
ret[i][j] = (char*) malloc(sizeof(char) * (strlen(e->element) + 1));
//*(ret[i] + j) = (char*) malloc(sizeof(char)* (strlen(strs[i]) + 1));
strcpy(ret[i][j], e->element);
//printf(" %s\n", ret[i][j]);
e = e->next;
}
p = p->next;
}
```
### 時間複雜度
### 【set】
* set：集合，去除重複的元素，資料由小到大排序。
* 宣告：
* set<int\> st;
* 把元素 x 加進 set：
* st.insert(x);
* 檢查元素 x 是否存在 set 中：
* st.count(x);
* 刪除元素 x：
* st.erase(x); // 可傳入值或iterator
* 清空集合中的所有元素：
* st.clear();
* 取值：使用iterator
* x = *st.begin(); // set 中的第一個元素(最小的元素)。
* x = *st.rbegin(); // set 中的最後一個元素(最大的元素)。
* 判斷是否為空的set：
* st.empty() 回傳true
* st.size() 回傳零
* 常用來搭配的member function：
* st.count(x);
* auto it = st.find(x); // binary search, O(log(N))
* auto it = st.lower_bound(x); // binary search, O(log(N))
* auto it = st.upper_bound(x); // binary search, O(log(N))
### 【multiset】
* 與 set 用法雷同，但會**保留重複的元素，資料由小到大排序。**
* 宣告：
* multiset<int\> st;
* 刪除資料：
* st.erase(val); 會刪除所有值為 val 的元素。
* st.erase(st.find(val)); 只刪除第一個值為 val 的元素。
## :memo: Design HashSet (Easy)
Design a HashSet without using any built-in hash table libraries.
Implement MyHashSet class:
* void add(key) Inserts the value key into the HashSet.
* bool contains(key) Returns whether the value key exists in the HashSet or not.
* void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.
### 作法 basic vector
```
class MyHashSet {
public:
vector<bool> hash_table;
MyHashSet() {
hash_table = vector<bool>(1000001, false);
}
void add(int key) {
hash_table[key] = true;
}
void remove(int key) {
hash_table[key] = false;
}
bool contains(int key) {
return hash_table[key] == true;
}
};
```
## :memo: Design HashMap (Easy)
Design a HashMap without using any built-in hash table libraries.
Implement the MyHashMap class:
* MyHashMap() initializes the object with an empty map.
* void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
* int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
* void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.
### 作法 basic vector
```
class MyHashMap {
public:
vector<int> hash_table;
MyHashMap() {
hash_table = vector<int>(1000001, -1);
}
void put(int key, int value) {
hash_table[key] = value;
}
int get(int key) {
return hash_table[key] == -1 ? -1 : hash_table[key];
}
void remove(int key) {
hash_table[key] = -1;
}
};
```
### 作法 最快code
```
class Node {
public:
int key, value;
Node* next;
Node(int k, int v, Node* nxt) {
key = k;
value = v;
next = nxt;
}
};
class MyHashMap {
public:
const static int CAPACITY = 1991;
const static int B = 997;
const static int P1 = 1937;
Node* data[CAPACITY] = {};
MyHashMap() {
}
int getHash(int key) {
return ((key * B) + P1) % CAPACITY;
}
void put(int key, int value) {
remove(key);
int h = getHash(key);
Node* node = new Node(key, value, data[h]);
data[h] = node;
}
int get(int key) {
int h = getHash(key);
Node* node = data[h];
while(node) {
if (node->key == key) {
return node->value;
}
node = node->next;
}
return -1;
}
void remove(int key) {
int h = getHash(key);
Node* node = data[h];
if (node == nullptr) {
return;
}
if (node->key == key) {
data[h] = node->next;
delete node;
}
else {
while(node && node->next) {
if (node->next->key == key) {
Node* temp = node->next;
node->next = temp->next;
delete temp;
}
node = node->next;
}
}
}
};
```
## :memo: 四、unordered_set C++
unordered_set 容器裡面的元素是唯一的，具有不重複的特性，而且是無排序的容器，unordered_set 容器裡面元素的值是不可修改，但 unordered_set 容器可以插入或刪除元素
### 初始化用法
```
#include <unordered_set>
//1.
unordered_set<int> myunordered_set{1, 2, 3, 4, 5};
//2.
int arr[] = {1, 2, 3, 4, 5};
unordered_set<int> myunordered_set(arr, arr+5);
```
### 插入元素與讀取元素 .insert()
```
unordered_set<int> myunordered_set;
myunordered_set.insert(1);
```
### 迴圈遍歷容器
```
unordered_set<int> myunordered_set = {3, 1};
myunordered_set.insert(2);
myunordered_set.insert(5);
myunordered_set.insert(4);
myunordered_set.insert(5);
myunordered_set.insert(4);
//迴圈
for (const auto &s : myunordered_set) {
std::cout << s << " ";
}
std::cout << "\n";
//4 5 2 1 3
//迭代器
for (std::unordered_set<int>::iterator it = myunordered_set.begin(); it != myunordered_set.end(); it++) {
// or
// for (auto it = myunordered_set.begin(); it != myunordered_set.end(); it++) {
std::cout << *it << " ";
}
std::cout << "\n";
```
### 刪除指定元素
```
unordered_set<int> myunordered_set{2, 4, 6, 8};
myunordered_set.erase(2);
for (const auto &s : myunordered_set) {
std::cout << s << " ";
}
std::cout << "\n";
//8 6 4
```
### 清空容器元素
```
myunordered_set.clear();
```
### 判斷元素是否存在 .count()
unordered_set 要判斷元素是否存在的話，可以使用 count()，存在回傳 1，不存在回傳 0
```
unordered_set<int> myunordered_set;
myunordered_set.insert(2);
myunordered_set.insert(4);
myunordered_set.insert(6);
std::cout << myunordered_set.count(4) << "\n"; // 1
std::cout << myunordered_set.count(8) << "\n"; // 0
```
### 判斷容器是否為空 .empty()
要判斷 unordered_set 是否為空或是裡面有沒有元素的話，可以用 empty()，寫法如下
```
unordered_set<int> myunordered_set;
myunordered_set.clear();
if (myunordered_set.empty()) {
std::cout << "empty\n";
} else {
std::cout << "not empty, size is "<< myunordered_set.size() <<"\n";
}
//empty
```
### 尋找元素 .find() .end()
如果找到是.end()代表不存在該元素
```
unordered_set<int> myunordered_set;
if (myunordered_set.find(99) == unordered_set.end()) { //代表不存在
cout<<"not exists!!"<<endl;
}
else {
cout<<"exists!!"<<endl;
}
```
## :memo: 五、HashSet - Usage C++
**要寫#include <unordered_set>**
```
#include <unordered_set>
int main() {
// 1. initialize a hash set
unordered_set<int> hashset;
// 2. insert a new key
hashset.insert(3);
hashset.insert(2);
hashset.insert(1);
// 3. delete a key
hashset.erase(2);
// 4. check if the key is in the hash set
if (hashset.count(2) <= 0) {
cout << "Key 2 is not in the hash set." << endl;
}
// 5. get the size of the hash set
cout << "The size of hash set is: " << hashset.size() << endl;
// 6. iterate the hash set
for (auto it = hashset.begin(); it != hashset.end(); ++it) {
cout << (*it) << " ";
}
cout << "are in the hash set." << endl;
// 7. clear the hash set
hashset.clear();
// 8. check if the hash set is empty
if (hashset.empty()) {
cout << "hash set is empty now!" << endl;
}
}
Finished in 3 ms
Key 2 is not in the hash set.
The size of hash set is: 2
1 3 are in the hash set.
hash set is empty now!
```
## :memo: Find Duplicates By HashSet (Easy)
Type是資料型態
```
bool findDuplicates(vector<Type>& keys) {
// Replace Type with actual type of your key
unordered_set<Type> hashset;
for (Type key : keys) {
if (hashset.count(key) > 0) {
return true;
}
hashset.insert(key);
}
return false;
}
```
## :memo: Single Number (Easy)
### 作法 Hash Table
**時間: O(N)**
**空間: O(N)**
```
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_set<int> hashset;
for (int num : nums) {
if (hashset.count(num) > 0) {
hashset.erase(num);
}
else {
hashset.insert(num);
}
}
for (int num : nums) {
if (hashset.count(num) == 1) {
return num;
}
}
return 0;
}
};
```
### 作法 Bit Manipulation
**時間: O(N)**
**空間: O(1)**
```
class Solution {
public:
int singleNumber(vector<int>& nums) {
int n = nums.size();
int ans = 0;
for (int i = 0; i < n; i++){
ans ^= nums[i];
}
return ans;
}
};
```
## :memo: 六、unordered_map C++
unordered_map 裡面的存放資料是無序的，unordered_map 對應雜湊表(hash table)，雜湊表的特點就是搜尋效率高，利用鍵值與雜湊函數(hash function)計算出雜湊值而快速的查找到對應的元素，時間複雜度為常數級別O(1)， 而額外空間複雜度則要高出許多。unordered_map 與 map 的使用方法基本上一樣，都是 key/value 之間的映射，只是他們內部採用的資料結構不一樣。所以對於需要高效率查詢的情況可以使用 unordered_map 容器。而如果對記憶體消耗比較敏感或者資料存放要求排序的話則可以用 map 容器。
### 初始化用法
```
#include <unordered_set>
unordered_map<string, int> umap = {{"Tom", 1}, {"Ann", 4}, {"Jack", 2}};
```
### 插入元素與讀取元素 .insert()
**第一種**是使用中括號 [] 的方式來插入元素，很像陣列的寫法，例如：umap[key] = value，範例如下
```
unordered_map<string, int> umap;
umap["John"] = 3;
```
**另一種**是使用 umap.insert() 成員函式來插入元素，
那這個 umap.insert() 方式跟上面中括號 [] 的方式有什麼不同呢？
差別在於如果 key 值已經存在的話，使用中括號 [] 的方式會將新資料覆蓋舊資料，
而使用 umap.insert() 的方式會回傳插入的結果，該 key 值存在的話會回傳失敗的結果，
檢查 umap.insert() 的插入結果方式如下
```
unordered_map<string, int> umap;
umap.insert(pair<string, int>("John", 3));
pair<unordered_map<string, int>, bool> retPair;
retPair = umap.insert(pair<string, int>("John", 3));
if (retPair.second == true)
cout << "Insert Successfully\n";
else
cout << "Insert Failure\n";
return 0;
```
### 容器裡移除元素 .erase()
移除第一個元素
```
unordered_map<string, int> umap;
umap.erase(umap.begin());
```
移除指定元素
```
unordered_map<string, int> umap;
umap.erase("Ann");
```
### 迴圈遍歷容器
```
//basic
for (auto it : hashmap) {
// print key
cout<<it.first<<" ";
// print value
cout<<it.second<<endl;
}
//迴圈
for (const auto& n : umap) {
cout << "name: " << n.first << ", id: " << n.second << "\n";
}
//迭代器
for (unordered_map<string, int> it = umap.begin(); it != umap.end(); it++) {
// or
// for (auto it = umap.begin(); it != umap.end(); it++) {
cout << "name: " << (*it).first << ", id: " << (*it).second << "\n";
}
```
### 清空容器元素 .clear()
```
unordered_map<string, int> umap;
umap.clear();
```
### 判斷容器是否為空 .empty()
要判斷 unordered_map 是否為空或是裡面有沒有元素的話，可以用 empty()，寫法如下
```
unordered_map<string, int> umap;
umap.clear();
if (umap.empty()) {
cout << "empty\n";
} else {
cout << "not empty, size is "<< umap.size() <<"\n";
}
//empty
```
### 尋找元素 .find() .end()
如果找到是.end()代表不存在該元素
```
unordered_map<string, int> umap;
if (umap.find("abc").end()) { //代表不存在
cout<<"not exists!!"<<endl;
}
else {
cout<<"exists!!"<<endl;
}
```
## :memo: 七、HashMap - Usage C++
**要寫#include <unordered_map>**
```
#include <unordered_map> // 0. include the library
int main() {
// 1. initialize a hash map
unordered_map<int, int> hashmap;
// 2. insert a new (key, value) pair
hashmap.insert(make_pair(0, 0));
hashmap.insert(make_pair(2, 3));
// 3. insert a new (key, value) pair or update the value of existed key
hashmap[1] = 1;
hashmap[1] = 2;
// 4. get the value of a specific key
cout << "The value of key 1 is: " << hashmap[1] << endl;
// 5. delete a key
hashmap.erase(2);
// 6. check if a key is in the hash map
if (hashmap.count(2) <= 0) {
cout << "Key 2 is not in the hash map." << endl;
}
// 7. get the size of the hash map
cout << "the size of hash map is: " << hashmap.size() << endl;
// 8. iterate the hash map
for (auto it = hashmap.begin(); it != hashmap.end(); ++it) {
cout << "(" << it->first << "," << it->second << ") ";
}
cout << "are in the hash map." << endl;
// 9. clear the hash map
hashmap.clear();
// 10. check if the hash map is empty
if (hashmap.empty()) {
cout << "hash map is empty now!" << endl;
}
}
```
## :memo: *Happy Number (Easy)
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
* Starting with any positive integer, replace the number by the sum of the squares of its digits.
* Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
* Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
### 作法1 Brute using unordered_map
```
int digitSqSum(int n) {
int sum = 0;
while (n > 0) {
sum = sum + ((n % 10) * (n % 10));
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
unordered_map<int, int> mp;
while (n != 1) {
if (mp[n] == 0) {
mp[n]++;
}
else {
return false;
}
n = digitSqSum(n);
}
return true;
}
```
### 作法2 Floyd's Cycle detection || Hare Tortoise algorithm
```
int digitSqSum(int n) {
int sum = 0;
while (n > 0) {
sum = sum + ((n % 10) * (n % 10));
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
int slow = digitSqSum(n);
int fast = digitSqSum(digitSqSum(n));
while (slow != fast) {
slow = digitSqSum(slow);
fast = digitSqSum(digitSqSum(fast));
}
return fast == 1;
}
```
### 作法3 記數字 1,89
Sum of squares of digits always ends in 1 or 89.
For example,
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
Any chain that arrives at 1 or 89 will become stuck in an endless loop.
So if the number is 89, we return false
```
int digitSqSum(int n) {
int sum = 0;
while (n > 0){
sum = sum + ((n % 10) * (n % 10));
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
int temp = n;
while (1) {
if (temp == 89) {
return false;
}
if (temp == 1) {
return true;
}
temp = digitSqSum(temp);
}
}
```
### 作法4 分析個位數
let's try different n:
true (1) -> 1
false (2) -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4
false (3) -> 9 -> 81 -> 65 -> 61 -> 37 (look at 2)
false (4) -> (look at 2)
false (5) -> 25 -> 29 -> 85 -> 89 (look at 2)
false (6) -> 36 -> 45 -> 41 -> 17 -> 50 -> 25 (look at 5)
true (7) -> 49 -> 97 -> 10
false (8) -> 64 -> 52 -> 29 (look at 5)
false (9) -> 9 -> 81 -> 65 (look at 3)
```
int digitSqSum(int n) {
int sum = 0;
while (n > 0) {
sum = sum + ((n % 10) * (n % 10));
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
while (true) {
long sum = digitSqSum(n);
if (1 <= sum && sum <= 9) {
if (sum == 1 || sum == 7) {
return true;
}
else {
return false;
}
}
else {
n = sum;
}
}
}
```
### 作法5 記數字1,4
A simple observation about the series:
All numbers eventually loop through either 1 or 4 before expanding further.
This approach was based on the idea that all numbers either end at 1 or enter the cycle {4, 16, 37, 58, 89, 145, 42, 20}, wrapping around it infinitely.
An alternative approach would be to recognise that all numbers will either end at 1, or go past 4 (a member of the cycle) at some point.
```
int digitSqSum(int n) {
int sum = 0;
while (n > 0) {
sum = sum + ((n % 10) * (n % 10));
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
if (n == 1) {
return true;
}
else if (n == 4) {
return false;
}
else {
return isHappy(digitSqSum(n));
}
}
```
## :memo: Two Sum (Easy)
### 作法
這題要把nums[i]放key，i放value
```
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); i++){
if (mp.find(target - nums[i]) == mp.end()) { //find=end代表hashtable沒有這個pair
mp[nums[i]] = i;
}
else {
return {mp[target - nums[i]], i};
}
}
return {-1, -1};
}
};
```
## :memo: Isomorphic Strings (Easy)
### 作法
一個英文字母會對應一個英文字母
```
class Solution {
public:
bool isIsomorphic(string s, string t) {
unordered_map<char, char> mp1, mp2;
for (int i = 0; i < s.length(); ++i) {
if (mp1[s[i]] && mp1[s[i]] != t[i]) return false;
if (mp2[t[i]] && mp2[t[i]] != s[i]) return false;
mp1[s[i]] = t[i];
mp2[t[i]] = s[i];
}
return true;
}
};
```
## :memo: Minimum Index Sum of Two Lists (Easy)
### 作法
用兩個hashmap，一個紀錄list1一個紀錄加總，範例code有map的coding的寫法，閱讀熟記:
```
class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
unordered_map<string, int> list1_m;
unordered_map<string, int> sums;
for(int i = 0; i < list1.size(); i++) {
list1_m[list1[i]] = i;
}
int minval = INT_MAX;
for(int i = 0; i < list2.size(); i++) {
auto iter = list1_m.find(list2[i]);
if (iter != list1_m.end()) {
sums[list2[i]] = iter->second + i;
if (sums[list2[i]] < minval) {
minval = sums[list2[i]];
}
}
}
vector<string> ans;
for(auto &e: sums) {
if (e.second == minval) {
ans.push_back(e.first);
}
}
return ans;
}
};
```
## :memo: First Unique Character in a String (Easy)
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
### 作法
```
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char, int> hashmap;
for (int i = 0; i < s.length(); i++) {
hashmap[s[i]]++;
}
for (int i = 0; i < s.length(); i++) {
if (hashmap[s[i]] == 1) {
return i;
}
}
return -1;
}
};
```
## :memo: Intersection of Two Arrays (Easy)
只要output交集元素，元素數量不用考慮
### 作法 Two sets
```
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> hashset1;
unordered_set<int> hashset2;
vector<int> ans;
for (int num : nums1) {
hashset1.insert(num);
}
for (int num : nums2) {
hashset2.insert(num);
}
for (int num : nums1) {
if (hashset1.count(num) == hashset2.count(num) && hashset1.count(num) != 0) {
hashset1.erase(num);
ans.push_back(num);
}
}
return ans;
}
};
```
## :memo: Intersection of Two Arrays II (Easy)
要output交集元素以及元素數量
### 作法 HashMap
```
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> hashmap;
vector<int> ans;
for (int i = 0; i < nums1.size(); i++) {
hashmap[nums1[i]]++;
}
for (int j = 0; j < nums2.size(); j++) {
if (hashmap[nums2[j]] > 0) {
hashmap[nums2[j]]--;
ans.push_back(nums2[j]);
}
}
return ans;
}
};
```
## :memo: Intersection of Multiple Arrays (Easy)
只要output交集元素，元素數量不用考慮
### 作法 Hash Table
```
class Solution {
public:
vector<int> intersection(vector<vector<int>>& nums) {
vector<int> count(1001, 0);
for(auto &x:nums) {
for(auto &y:x) {
count[y]++;
}
}
vector<int> ans;
for (int i = 1; i <= 1000; i++) {
if (count[i] == nums.size()) {
ans.push_back(i);
}
}
return ans;
}
};
```
## :memo: Intersection of Three Sorted Arrays (Easy)
只要output交集元素，元素數量不用考慮
### 作法 Brute Force with Hashmap
```
class Solution {
public:
vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
int max_value = max(max(arr1[arr1.size() - 1], arr2[arr2.size() - 1]), arr3[arr3.size() - 1]);
vector<int> hashtable(max_value + 1, 0);
for (auto& n : arr1) {
hashtable[n]++;
}
for (auto& n : arr2) {
hashtable[n]++;
}
for (auto& n : arr3) {
hashtable[n]++;
}
vector<int> ans;
for (int i = 1; i < hashtable.size(); i++) {
if (hashtable[i] == 3) {
ans.push_back(i);
}
}
return ans;
}
};
```
### 作法 Three Pointers
這個if else好讚
```
class Solution {
public:
vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
vector<int> ans;
int p1 = 0, p2 = 0, p3 = 0;
int Length1 = arr1.size(), Length2 = arr2.size(), Length3 = arr3.size();
while (p1 < Length1 and p2 < Length2 and p3 < Length3) {
if (arr1[p1] == arr2[p2] and arr2[p2] == arr3[p3]) {
ans.push_back(arr1[p1]);
p1++;
p2++;
p3++;
} else {
if (arr1[p1] < arr2[p2]) {
p1++;
} else if (arr2[p2] < arr3[p3]) {
p2++;
} else {
p3++;
}
}
}
return ans;
}
};
```
## :memo: Contains Duplicate (Easy)
Given an integer array nums, return **true if any value appears at least twice in the array**, and return **false if every element is distinct**.
### 作法 HashSet
**時間: O(N)**
**空間: O(N)**
```
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> hashset;
for (int num : nums) {
if (hashset.count(num) > 0) {
return true;
}
hashset.insert(num);
}
return false;
}
};
```
## :memo: Contains Duplicate II (Easy)
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
### 作法
要寫**hashmap.count(nums[i])** && abs(hashmap[nums[i]] - i) <= k
```
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> hashmap;
for (int i = 0; i < nums.size(); i++) {
if (hashmap.count(nums[i]) && abs(hashmap[nums[i]] - i) <= k) {
return true;
}
hashmap[nums[i]] = i;
}
return false;
}
};
```
## :memo: Contains Duplicate III (Hard)
You are given an integer array nums and two integers indexDiff and valueDiff.
Find a pair of indices (i, j) such that:
* i != j,
* abs(i - j) <= indexDiff.
* abs(nums[i] - nums[j]) <= valueDiff, and
Return true if such pair exists or false otherwise.
### 作法 Naive Linear Search (Time Limit Exceeded)
```
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
for (int i = 0; i <= nums.size(); i++) {
int j = i + 1;
while (j - i <= indexDiff and j < nums.size()) {
if (abs(nums[i] - nums[j]) <= valueDiff) {
return true;
}
j++;
}
}
return false;
}
};
```
### 作法 Binary Search Tree multiset
動態的調整index範圍內最小值最大值，只有index在範圍內的數值才要算在內
**時間: O(nlog(min(n,k)))**
**空間: O(min(n,k))**
Figure 1. A non-balanced BST that is skewed to the left.
Figure 2. A balanced BST.
```
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
if (nums.size() == 0) {
return false;
}
if (indexDiff == 0) {
return false;
}
multiset<int> bst;
for (int i = 0; i < nums.size(); i++) {
const auto it = bst.lower_bound(nums[i] - valueDiff);
if (it != bst.end() and abs(*it - nums[i]) <= valueDiff) {
return true;
}
bst.insert(nums[i]);
if (bst.size() > indexDiff) {
bst.erase(bst.find(nums[i - indexDiff]));
}
}
return false;
}
};
```
### 作法 Buckets (Bucket sort)
利用正負1個水桶記錄index範圍內，GetID算現在的nums[i]是哪個水桶(key)，每個水桶放valueDiff大小區間
**Any two elements that are not in the same or adjacent buckets must have a distance greater than t.**
**時間: O(n)**
**空間: O(min(n,k))**
Figure 3. Illustration of buckets.
```
class Solution {
public:
long getID(long x, long w) {
return x < 0 ? (x + 1) / w - 1 : x / w;
}
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
if (valueDiff < 0) {
return false;
}
map<long, long> mp;
long w = (long) valueDiff + 1;
for (int i = 0; i < nums.size(); i++) {
long m = getID(nums[i], w);
// check if bucket m is empty, each bucket may contain at most one element
if (mp.find(m) != mp.end()) {
return true;
}
// check the neighbor buckets for almost duplicate
if (mp.find(m - 1) != mp.end() and abs(nums[i] - mp[m - 1]) < w) {
return true;
}
if (mp.find(m + 1) != mp.end() and abs(nums[i] - mp[m + 1]) < w) {
return true;
}
// now bucket m is empty and no almost duplicate in neighbor buckets
mp[m] = (long) nums[i];
// 太遠的水桶就不要了
if (i >= indexDiff) {
mp.erase(getID(nums[i - indexDiff], w));
}
}
return false;
}
};
```
## :memo: Logger Rate Limiter (Easy)
Design a logger system that receives a stream of messages along with their timestamps. Each unique message should only be printed at most every 10 seconds (i.e. a message printed at timestamp t will prevent other identical messages from being printed until timestamp t + 10).
All messages will come in chronological order. Several messages may arrive at the same timestamp.
Implement the Logger class:
* Logger() Initializes the logger object.
* bool shouldPrintMessage(int timestamp, string message) Returns true if the message should be printed in the given timestamp, otherwise returns false.
### 作法
```
class Logger {
public:
unordered_map<string, int> hashmap;
// 這個Logger()空白就好XD
Logger() {
}
bool shouldPrintMessage(int timestamp, string message) {
if (hashmap[message] <= timestamp) {
hashmap[message] = timestamp + 10;
return true;
}
else if (hashmap[message] + 10 > timestamp) {
return false;
}
else if (hashmap[message] == 0) {
hashmap[message] = timestamp + 10;
return true;
}
return false;
}
};
```
## :memo: Group Anagrams (Medium)
### 作法
利用C++的sort把str[i]排序後當key，這樣就是唯一順序(key)，每個排序後有了key就把str[i]加到mp[key]中
```
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> ans;
unordered_map<string, vector<string>> mp;
/*
Consider example 1 : strs = ["eat","tea","tan","ate","nat","bat"]
After the below opeartion of for loop map will contain
aet -- eat, tea, ate
ant -- tan, nat
abt -- bat
*/
for (int i = 0; i < strs.size(); i++) {
string s = strs[i];
sort(strs[i].begin(),strs[i].end());
mp[strs[i]].push_back(s);
}
// now simply put the elements of second column of map in ans
for (auto i : mp) {
ans.push_back(i.second);
}
return ans;
}
};
```
## :memo: Group Shifted Strings (Medium)
We can shift a string by shifting each of its letters to its successive letter.
* For example, "abc" can be shifted to be "bcd".
We can keep shifting the string to form a sequence.
* For example, we can keep shifting "abc" to form the sequence: "abc" -> "bcd" -> ... -> "xyz".
Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.
### 作法
這題要寫獨特的hash function，計算字串間的字母大小的相對差值，key具備唯一性
```
class Solution {
public:
string getHash(string &s) {
string hashKey;
for (int i = 1; i < s.length(); i++) {
hashKey += (s[i] - s[i - 1] + 26) % 26 + 'a';
}
return hashKey;
}
vector<vector<string>> groupStrings(vector<string>& strings) {
unordered_map<string, vector<string>> mapHashToList;
for (string str : strings) {
string hashKey = getHash(str);
mapHashToList[hashKey].push_back(str);
}
vector<vector<string>> groups;
for (auto it : mapHashToList) {
groups.push_back(it.second);
}
return groups;
}
};
```
## :memo: Valid Sudoku (Medium)
### 作法 C
利用大小9的bucket去記錄數字(1~9)出現次數，第一個nested-for檢查一橫一橫，第二個nested-for檢查一豎一豎，最後檢查小block
```
bool checklittleblock(int row, int col, char** board)
{
int bucket[9] = {0};
for(int i = row - 3; i < row; i++)
{
for(int j = col - 3; j < col; j++)
{
if(board[i][j] != 46)
{
bucket[board[i][j] - 49]++;
}
}
}
for(int j = 0; j < 9; ++)
{
if(bucket[j] > 1)
{
return false;
}
}
return true;
}
bool isValidSudoku(char** board, int boardSize, int* boardColSize){
int bucket[9] = {0};
bool ret = true;
for(int i = 0; i < boardSize; i++)
{
for(int j = 0; j < *boardColSize; j++)
{
if(board[i][j] != 46)
{
bucket[board[i][j] - 49]++;
}
}
for(int j = 0; j < *boardColSize; j++)
{
if(bucket[j] > 1)
{
return false;
}
}
memset(bucket, 0, sizeof(bucket));
}
for(int i = 0; i < boardSize; i++)
{
for(int j = 0; j < *boardColSize; j++)
{
if(board[j][i] != 46)
{
bucket[board[j][i] - 49]++;
}
}
for(int j = 0; j < *boardColSize; j++)
{
if(bucket[j] > 1)
{
return false;
}
}
memset(bucket, 0, sizeof(bucket));
}
int row = 3;
int col = 3;
for(int i = row; i <= 9; i+=3)
{
for(int j = col; j <= 9; j+=3)
{
ret = checklittleblock(i, j, board);
if(ret == false)
{
return false;
}
}
}
return ret;
}
```
## :memo: Find Duplicate Subtrees (Medium)
### 作法
The function traverse(node) traverses the subtree of node and adds duplicate subtrees to the answer. The return value is the ID of the subtree.
The function works as follows:
1. Traverse the left subtree of the node and get its ID (call recursively traverse(node->left)).
2. Traverse the right subtree of the node and get its ID (call recursively traverse(node->right)).
3. Compose a triplet of the following values: the left subtree ID, the value of the node, and the right subtree ID.
4. If the triplet is not in the hash map tripletToID, we assign a new ID to this triplet – the smallest unused non-negative integer value (we can use the length of the map for this). Otherwise, get the ID from tripletToID.
5. If the ID occurs for the second time, it means there was already the same subtree as the current one (the subtree of node). In this case, we add node to the answer.
6. Return the ID from the function.
We only need to call traverse(root) to solve the problem.
```
class Solution {
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
unordered_map<string, int> tripletToID;
unordered_map<int, int> cnt;
vector<TreeNode*> res;
function<int(TreeNode*)> traverse = [&tripletToID, &cnt, &res, &traverse](TreeNode* node) -> int {
if (node == nullptr) {
return 0;
}
string triplet = to_string(traverse(node->left)) + "," + to_string(node->val) + "," + to_string(traverse(node->right));
if (!tripletToID.count(triplet)) {
tripletToID[triplet] = tripletToID.size() + 1;
}
int id = tripletToID[triplet];
cnt[id]++;
if (cnt[id] == 2) {
res.push_back(node);
}
return id;
};
traverse(root);
return res;
}
};
```
### 作法 DFS and HashMap (easy to memorize)
```
class Solution {
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
unordered_map<string, int>m;
vector<TreeNode*>res;
DFS(root, m, res);
return res;
}
string DFS(TreeNode* root, unordered_map<string, int>& m, vector<TreeNode*>& res){
if(!root) return "";
string s = to_string(root->val) + "," + DFS(root->left, m, res) + "," + DFS(root->right, m, res);
if(m[s]++ == 1) res.push_back(root);
return s;
}
};
```
## :memo: 八、Design the Key - Summary
Here are some takeaways about how to design the key for you.
1. When the order of each element in the string/array doesn't matter, you can use the sorted string/array as the key.
2. If you only care about the offset of each value, usually the offset from the first value, you can use the offset as the key.
3. In a tree, you might want to directly use the TreeNode as key sometimes. But in most cases, the serialization of the subtree might be a better idea.
4. In a matrix, you might want to use the row index or the column index as key.
5. In a Sudoku, you can combine the row index and the column index to identify which block this element belongs to.
6. Sometimes, in a matrix, you might want to aggregate the values in the same diagonal line.
## :memo: 九、Conclusion
What's more, we will meet more complicated problems sometimes. We might need to:
* use several hash tables together
* combine the hash table with other data structure
* combine the hash table with other algorithms
* ...
## :memo: Jewels and Stones (Easy)
看有幾顆石頭是寶石
### 作法 HashSet
```
class Solution {
public:
int numJewelsInStones(string jewels, string stones) {
unordered_set<char> hashset;
int count = 0;
for (char c : jewels) {
if (hashset.count(c) > 0) {
continue;
}
hashset.insert(c);
}
for (char c : stones) {
if (hashset.count(c) > 0) {
count++;
}
}
return count;
}
};
```
## :memo: Longest Substring Without Repeating Characters (Medium)
Given a string s, find the length of the longest substring without repeating characters.
### 作法 Sliding window Optimized
**時間: O(N)**
**空間: O(min(M,N))**
記錄字母出現的index，遇到重複字母就更新index索引值，並且更新最長的不重複字母的字串長度
```
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = int(s.length());
int res = 0;
unordered_map<char, int> mp;
for (int j = 0, i = 0; j < n; j++) {
if (mp[s[j]] > 0) {
i = max(mp[s[j]], i);
}
res = max(res, j - i + 1);
mp[s[j]] = j + 1;
}
return res;
}
};
```
## :memo: Two Sum III - Data structure design (Easy)
### 作法
用hashmap去記錄，**原來for可以遍歷hashmap**
```
class TwoSum {
unordered_map<int, int> hash;
public:
TwoSum() {
}
void add(int number) {
hash[number]++;
}
bool find(int value) {
for (auto h : hash) {
long val = value;
if (val == h.first * 2) {
if (h.second >= 2) return true;
} else {
if (hash.find(val - h.first) != hash.end()) return true;
}
}
return false;
}
};
```
## :memo: 4Sum II (Medium)
### 作法
可以用在kSum II，5Sum II或6Sum II都行，看熟
```
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
vector<vector<int>> lsts = {nums1, nums2, nums3, nums4};
int k = int(lsts.size());
auto countSum = [&](int start, int end) {
map<int, int> cnt({{0, 1}});
for (int i = start; i < end; i++) {
map<int, int> temp;
for (int total : lsts[i]) {
for (auto k = cnt.begin(); k != cnt.end(); k++) {
temp[total + k->first] += k->second;
}
}
cnt = temp;
}
return cnt;
};
map<int, int> left = countSum(0, k / 2);
map<int, int> right = countSum(k / 2, k);
int res = 0;
for (auto k = left.begin(); k != left.end(); k++) {
res += k->second * right[-k->first];
}
return res;
}
};
```
### 作法 HashMap
```
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
int cnt = 0;
unordered_map<int, int> m;
for (int a : A) {
for (int b : B) {
++m[a + b];
}
}
for (int c : C) {
for (int d : D) {
auto it = m.find(-(c + d));
if (it != end(m)) {
cnt += it->second;
}
}
}
return cnt;
}
};
```
## :memo: Top K Frequent Elements (Medium)
### 作法 Quickselect (Hoare's selection algorithm)
Quickselect is a textbook algorithm
typically used to solve the problems "find kth something":
* kth smallest
* kth largest
* kth most frequent
* kth less frequent
Like quicksort, quickselect was developed by Tony Hoare, and also known as Hoare's selection algorithm.
It has O(N) average time complexity and is widely used
in practice. It worth noting that its worst-case time complexity
is O(N^2), although the probability of this worst-case is negligible.
**時間: O(N)**
**空間: O(N)**
```
class Solution {
private:
vector<int> unique;
map<int, int> count_map;
public:
int partition(int left, int right, int pivot_index) {
int pivot_frequency = count_map[unique[pivot_index]];
// 1. move pivot to the end
swap(unique[pivot_index], unique[right]);
// 2. mave all less frequent elements to the left
int store_index = left;
for (int i = left; i <= right; i++) {
if (count_map[unique[i]] < pivot_frequency) {
swap(unique[store_index], unique[i]);
store_index += 1;
}
}
// 3. move pivot to its final place
swap(unique[right], unique[store_index]);
return store_index;
}
void quickselect(int left, int right, int k_smallest) {
/*
Sort a list within left..right till kth less frequent element
takes its place
*/
// base case: the list contains only one element
if (left == right) {
return;
}
int pivot_index = left + rand() % (right - left + 1);
// find the pivot position in a sorted list
pivot_index = partition(left, right, pivot_index);
// if the pivot is in its final sorted position
if (k_smallest == pivot_index) {
return;
}
else if (k_smallest < pivot_index) {
// go left
quickselect(left, pivot_index - 1, k_smallest);
}
else {
// go right
quickselect(pivot_index + 1, right, k_smallest);
}
}
vector<int> topKFrequent(vector<int>& nums, int k) {
// build hash map : element and how often it appears
for (int n : nums) {
count_map[n] += 1;
}
// array of unique elements
int n = count_map.size();
for (pair<int, int> p : count_map) {
unique.push_back(p.first);
}
// kth top frequent element is (n - k)th less frequent.
// Do a partial sort: from less frequent to the most frequent, till
// (n - k)th less frequent element takes its place (n - k) in a sorted array.
// All element on the left are less frequent.
// All the elements on the right are more frequent.
quickselect(0, n - 1, n - k);
// Return top k frequent elements
vector<int> top_k_frequent(k);
copy(unique.begin() + n - k, unique.end(), top_k_frequent.begin());
return top_k_frequent;
}
};
```
## :memo: Unique Word Abbreviation (Medium)
The abbreviation of a word is a concatenation of its first letter, the number of characters between the first and last letter, and its last letter. If a word has only two characters, then it is an abbreviation of itself.
For example:
* dog --> d1g because there is one letter between the first letter 'd' and the last letter 'g'.
* internationalization --> i18n because there are 18 letters between the first letter 'i' and the last letter 'n'.
* it --> it because any word with only two characters is an **abbreviation** of itself.
Implement the ValidWordAbbr class:
* ValidWordAbbr(String[] dictionary) Initializes the object with a dictionary of words.
* boolean isUnique(string word) Returns true if **either** of the following conditions are met (otherwise returns false):
* There is no word in dictionary whose **abbreviation** is equal to word's abbreviation.
* For any word in dictionary whose **abbreviation** is equal to word's **abbreviation**, that word and word are **the same**.
**Input:**
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
**Output:**
[null, false, true, false, true, true]
**Explanation**
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.
### 作法
```
class ValidWordAbbr {
private:
unordered_map<string, unordered_set<string>> mp;
public:
ValidWordAbbr(vector<string>& dictionary) {
for (string& d : dictionary) {
int n = d.length();
string abbr = d[0] + to_string(n) + d[n - 1];
mp[abbr].insert(d);
}
}
bool isUnique(string word) {
int n = word.length();
string abbr = word[0] + to_string(n) + word[n - 1];
return mp[abbr].count(word) == mp[abbr].size();
}
};
```
## :memo: Insert Delete GetRandom O(1) (Medium)
Implement the RandomizedSet class:
* RandomizedSet() Initializes the RandomizedSet object.
* bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
* bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
* int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the **same probability** of being returned.
You must implement the functions of the class such that each function works in **average** O(1) time complexity.
**Input:**
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
**Output:**
[null, true, false, true, 2, true, false, 2]
**Explanation**
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
### 作法
**advance(it, n)**:
it表示某個迭代器，n為整數。該函數的功能是將 it 迭代器前進n個位置(n>0)或後退n個位置(n<0)。
```
class RandomizedSet {
private:
unordered_set<int> set;
public:
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool insert(int val) {
if (set.find(val) != set.end()) return false;
set.insert(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val) {
if (set.find(val) == set.end()) return false;
set.erase(val);
return true;
}
/** Get a random element from the set. */
int getRandom() {
const int i = rand() % set.size();
auto itr = set.begin();
advance(itr, i); // get to random index i
return *itr;
}
};
```
## :memo: LRU Cache (Medium)
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
### 作法 STL
```
class LRUCache {
public:
unordered_map<int, list<pair<int, int>>::iterator> dic;
list<pair<int, int>> lru;
int size = 0;
LRUCache(int capacity) {
size = capacity;
}
int get(int key) {
auto it = dic.find(key);
if (it == dic.end()) {
return -1;
}
int value = it->second->second;
lru.erase(it->second);
lru.push_front({key, value});
dic.erase(it);
dic[key] = lru.begin();
return value;
}
void put(int key, int value) {
auto it = dic.find(key);
if (dic.find(key) != dic.end()) {
lru.erase(it->second);
dic.erase(it);
}
lru.push_front({key, value});
dic[key] = lru.begin();
if (dic.size() > size) {
auto it = dic.find(lru.rbegin()->first);
dic.erase(it);
lru.pop_back();
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
```
## :memo: Majority Element (Easy)
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than **⌊n / 2⌋** times. You may assume that the majority element always exists in the array.
這題做法一堆: Brute Force, HashMap, Sorting, Bit Manipulation, Divide and Conquer, Boyer-Moore Voting Algorithm
難度: Bit Manipulation, Divide and Conquer, Sorting, Boyer-Moore Voting, Brute Force, HashMap
### 作法 Brute Force
**時間: O(N^2)**
**空間: O(1)**
```
class Solution {
public int majorityElement(int[] nums) {
int majorityCount = nums.length/2;
for (int num : nums) {
int count = 0;
for (int elem : nums) {
if (elem == num) {
count += 1;
}
}
if (count > majorityCount) {
return num;
}
}
return -1;
}
}
```
### 作法 HashMap
**時間: O(N)**
**空間: O(N)**
```
class Solution {
private Map<Integer, Integer> countNums(int[] nums) {
Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
for (int num : nums) {
if (!counts.containsKey(num)) {
counts.put(num, 1);
}
else {
counts.put(num, counts.get(num)+1);
}
}
return counts;
}
public int majorityElement(int[] nums) {
Map<Integer, Integer> counts = countNums(nums);
Map.Entry<Integer, Integer> majorityEntry = null;
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
majorityEntry = entry;
}
}
return majorityEntry.getKey();
}
}
```
### 作法 Sorting
**時間: O(NlgN)**
**空間: O(1)**
```
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
```
### 作法 Bit Manipulation
**時間: O(NlgC)**
**空間: O(N)**
C is the max absolute value in nums, i.e., 10^5 in this problem. We enumerate all logC bits for each number in nums.
```
class Solution {
public int majorityElement(int[] nums) {
int n = nums.length;
int majority_element = 0;
for (int i = 0; i < 32; i++) {
int bit = 1 << i;
// Count how many numbers have this bit set.
int bit_count = 0;
for (int num : nums) {
if ((num & bit) != 0) {
bit_count++;
}
}
// If this bit is present in more than n / 2 elements
// then it must be set in the majority element.
if (bit_count > n / 2) {
majority_element |= bit;
}
}
return majority_element;
}
}
```
### 作法 Divide and Conquer
**時間: O(NlgN)**
**空間: O(lgN)**
```
class Solution {
private int countInRange(int[] nums, int num, int lo, int hi) {
int count = 0;
for (int i = lo; i <= hi; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
private int majorityElementRec(int[] nums, int lo, int hi) {
// base case; the only element in an array of size 1 is the majority
// element.
if (lo == hi) {
return nums[lo];
}
// recurse on left and right halves of this slice.
int mid = (hi-lo)/2 + lo;
int left = majorityElementRec(nums, lo, mid);
int right = majorityElementRec(nums, mid+1, hi);
// if the two halves agree on the majority element, return it.
if (left == right) {
return left;
}
// otherwise, count each element and return the "winner".
int leftCount = countInRange(nums, left, lo, hi);
int rightCount = countInRange(nums, right, lo, hi);
return leftCount > rightCount ? left : right;
}
public int majorityElement(int[] nums) {
return majorityElementRec(nums, 0, nums.length-1);
}
}
```
### 作法 Boyer-Moore Voting Algorithm
**時間: O(N)**
**空間: O(1)**
```
class Solution {
public:
int majorityElement(vector<int>& nums) {
// Boyer-Moore Voting Algorithm
int count = 0;
int candiate = 0;
for (int n : nums) {
if (count == 0) {
candiate = n;
}
count += (n == candiate) ? 1 : -1;
}
return candiate;
}
};
```
## :memo: Majority Element II (Medium)
Given an integer array of size n, find all elements that appear more than **⌊ n/3 ⌋** times.
### 作法 Boyer-Moore Voting Algorithm
**時間: O(N)**
**空間: O(1)**
```
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
// Boyer-Moore Voting Algorithm
// 1st pass
int count1 = 0;
int count2 = 0;
long candidate1 = LONG_MIN;
long candidate2 = LONG_MIN;
for (int n : nums) {
if (candidate1 != LONG_MIN and candidate1 == n) {
count1++;
} else if (candidate2 != LONG_MIN and candidate2 == n) {
count2++;
} else if (count1 == 0) {
candidate1 = n;
count1++;
} else if (count2 == 0) {
candidate2 = n;
count2++;
} else {
count1--;
count2--;
}
}
// 2nd pass
vector<int> result;
count1 = 0;
count2 = 0;
for (int n : nums) {
if (candidate1 != LONG_MIN and n == candidate1) count1++;
if (candidate2 != LONG_MIN and n == candidate2) count2++;
}
int sz = nums.size();
if (count1 > sz / 3) result.push_back(candidate1);
if (count2 > sz / 3) result.push_back(candidate2);
return result;
}
};
```
## :memo: 刷題檢討
有很多題目根本寫不出來，最後看Discuss才了解要怎麼寫，用C寫hash table太複雜，對於coding不熟練是無法輕易用C去解題，(key,value)要放nums的(索引,數值)還是(數值,索引)要依照題目要求去思考，第一個for迴圈通常是將nums轉成mp，如果可以在第一個for迴圈就得出結果意味著不用跑完整個nums就能結束，如果題目有兩個以上的nums則有可能需要準備兩個以上的mp去做解題。
Sign in with Wallet
Connect another wallet