# Ch24 將陣列作為表格用途
> 搭配 [Leetcode 解題系統](https://leetcode.com/)
> 回目錄:[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)
## <font color='darkblue'>將陣列作為表格用途</font>
後面的幾個章節要學的是「表格」類型的資料結構
包括 unordered_map / unordered_set (沒有順序的表格)
和 map / set (有順序的表格)
在正式開始介紹這四樣資料結構前
我們先來熟悉一些概念類似,但不需要用到這些資料結構的題目
## <font color='darkblue'>適用題型:計數問題</font>
如果要統計每種數字共出現幾次
我們可以使用一個陣列來記錄
陣列的第`k`格紀錄的就是「數字`k`共出現了幾次」
### <font color='#0047AB'>有明確數值範圍</font>
<font color='darkorange'>【例題】</font>
> 題目給一個名為 nums 的一維陣列,裡面共有 `n` 個數字
> 剛好在 `1` 到 `n` 這 `n` 個數字裡面
> 有一個數字重複了,有一個數字缺失了,其他都正好出現一次
> 請找出重複的數字和缺失的數字並回傳
> 例如 [1, 2, 2, 4] 就是 2 重複了,3 不見了
> 所以要回傳 [2, 3]
這是 Leetcode 上的題目,連結是 [Leetcode 645](https://leetcode.com/problems/set-mismatch/)
我們可以用一個長度為 n+1 的 vector 來當作表格做計數,命名為 `count`
之所以會需要 n+1 格是因為這樣才有第 n 格可以使用 (而第0格用不到)
每一格都要先歸零
```cpp=
int n = nums.size();
vector<int> count(n+1, 0);
// n+1格 每格為0
```
然後就拜訪 `nums` 裡的每個值
把 `count` 裡對應的格子 +1
```cpp=4
for(int i=0;i<nums.size();i++){
count[nums[i]]++;
}
```
最後再從 1 至 n 檢查一遍 `count`
是哪個數字出現兩次?是哪個數字出現0次?分別存到 ans 的第 0 和第 1 格
```cpp=7
vector<int> ans(2);
for(int i=1;i<=n;i++){
if(count[i]==2) ans[0]=i;
if(count[i]==0) ans[1]=i;
}
return ans;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2965: 重複的數字與缺失的數字 ](https://leetcode.com/problems/find-missing-and-repeated-values/)
>
> 題目給我們一個名為 grid 的二維 vector,尺寸是 `n*n`
> 裡面剛好是 `1` 至 `n*n` 這些數字裡面
> 一個重複,一個缺失,其他正好出現一次
> 請找出重複的數字和缺失的數字
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2784: n有兩個,其他各一個 ](https://leetcode.com/problems/check-if-array-is-good/)
>
> 題目給一個名為 nums 的一維陣列,長度是 n+1
> 請問是否這 n+1 個數字裡面,n 總共有兩個
> 且 1, 2, ..., n-1 這些數字各有一個呢?
首先令 n 為 nums.size()-1,就可以建立表格做計數
請注意 nums 裡面可能會有比 n 大的值,若看到了就要立刻回傳 false
不要放進計數表格裡(因為表格裡沒有他對應的格子!)
### <font color='#0047AB'>沒有明確數值範圍</font>
上述的例題和類題都能夠從 input 推論出數值的範圍
例如例題的數字是 1 至 n,所以我們可以準備長度為 n+1 的陣列來計數
類題的數字是 1 至 n\*n,所以我們可以準備長度為 n\*n+1 的陣列來計數...
若是沒辦法直接從 input 推論出數值範圍
我們可以依據題目保證的數值大小來準備計數的陣列
<font color='darkorange'>【例題】</font>
> 題目給一個名為 arr 的一維陣列
> 若有個數字 x 在 arr 裡出現的次數正好為 x 次
> 那麼 x 就是個幸運數字
> 請找出最大的幸運數字並回傳
> 如果幸運數字不存在,請回傳 -1
這是 Leetcode 上的題目,連結是 [Leetcode 1394](https://leetcode.com/problems/find-lucky-integer-in-an-array/)
因為題目裡有保證說 arr 裡面的數字最大為 500
我們就可以開一個大小為 501 的陣列來幫助計數
```cpp=
// 長度固定為 501 的陣列,全部歸零
int count[501] = {0};
// 拜訪 arr 裡面的每個數,記錄出現次數
for(int i=0;i<arr.size();i++){
count[arr[i]]++;
}
// 從最大的數字 500 檢查到最小的數字 1
for(int i=500;i>=1;i--){
// 一旦發現幸運數字即可回傳
if(count[i]==i) return i;
}
// 若迴圈結束後都沒有數字被回傳,代表沒有幸運數字
return -1;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 961: 出現了n次的數字 ](https://leetcode.com/problems/n-repeated-element-in-size-2n-array/)
>
> 題目給一個陣列共有 2n 個數字,其中有 n 個數字是相同的,其餘皆不同
> 請找出出現了 n 次的那個數字
提示:
題目保證數字範圍不超過10000,所以可以用長度為 10001 的陣列計數
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 3046: 有人出現超過兩次嗎 ](https://leetcode.com/problems/split-the-array/)
>
> 題目給一個名為 nums 的陣列,請判斷是否能把這些數字分成兩堆,且兩堆裡面都沒有重複的數字
也就是說,如果 nums 裡面有數字重複了超過兩次,就不可以,否則就可以
題目保證數字範圍不超過100,所以可以用長度為 101 的陣列計數
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 1748: 出現一次的數字之和 ](https://leetcode.com/problems/sum-of-unique-elements/)
>
> 題目給一個名為 nums 的陣列,請找出所有「只出現一次」的數字,並算出這些數字的總和
先計數,再看看有哪些數字出現次數為1,將它們加總
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2248: 在每一行都有出現的數字 ](https://leetcode.com/problems/intersection-of-multiple-arrays/)
>
> 題目給一個二維陣列 nums
> nums 裡面的每一個一維陣列裡都沒有重複的數字
> 但是會有些數字同時出現在多個一維陣列裡
> 請找出所有這樣的數字
可以統計 nums 裡每個數字出現的次數,並找出所有出現次數為`nums.size()`的數字
注意題目要求回傳的是依照小排到大的陣列,因此最後迴圈可以從小的數字往大的數字逐一拜訪
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 997: 找出秘密法官 ](https://leetcode.com/problems/find-the-town-judge/)
>
> 村裡有 n 個人,編號為 1 到 n,其中有一個人是法官
> 法官不相信任何人,且法官以外的所有人都相信法官
> 題目給一個數字 n 和一個二維陣列 trust
> trust 裡面的每一行都代表「編號為 trust[i][0] 的人」相信「編號為 trust[i][1] 的人」
> 請依據判斷誰是法官的規則,找出法官
可以用兩個陣列,一個統計每個人「相信幾個人」
另一個統計每個人「被幾個人相信」
最後再找出誰「相信0個人且被n-1個人相信著」
### <font color='#0047AB'>區間問題</font>
<font color='darkorange'>【例題】</font>
> 題目給一個二維陣列 ranges
> 對於每一個 ranges[i],它代表從 ranges[i][0] 到 ranges[i][1] 的範圍都被覆蓋了
> 題目還給了一個 left 和一個 right
> 請問從 left 到 right 的整個範圍都有被覆蓋到嗎?
這是 Leetcode 上的題目,連結是 [Leetcode 1893](https://leetcode.com/problems/check-if-all-the-integers-in-a-range-are-covered/)
我們可以用一個 bool 的陣列來代表每一個座標有沒有被覆蓋到
把 ranges 裡的每個線段都蓋上去
再從 left 到 right 依序檢查是否有任何一個座標沒被覆蓋
題目表示了座標都在 1 到 50 的範圍內,所以用長度為 51 的陣列即可
```cpp=
bool covered[51] = {false}; // 先全部設為 false
for(int i=0;i<ranges.size();i++){
// 被每個 ranges 覆蓋到的座標,都設為 true
for(int j=ranges[i][0];j<=ranges[i][1];j++) covered[j] = true;
}
// 從 left 檢查到 right
for(int i=left;i<=right;i++){
// 如果有任何一處沒被覆蓋,回傳 false
if(!covered[i]) return false;
}
// 都檢查完了,代表都有覆蓋到
return true;
```
## <font color='darkblue'>適用題型:配對或分配問題</font>
剛才的題目只關注哪些人的數量符合條件
接下來的題目要用到所有人的數量,來達成配對或分配
### <font color='#0047AB'>平分問題</font>
<font color='darkorange'>【例題】</font>
> 題目給一個名為 words 的陣列
> 裡面有k個字串,每個都由小寫英文字母組成
> 請問能不能把這些字串裡面的所有英文字母重新分配成k組
> 使得每一組裡面的英文字母種類數量都相同呢?
> 例如 ["ab","aabc","bcc"] 可以重新分配成三組,每組有 a, b, c 各一個
這是 Leetcode 上的題目,連結是 [Leetcode 1897](https://leetcode.com/problems/redistribute-characters-to-make-all-strings-equal/)
要判斷一堆英文字母能不能平分成 k 組
我們要檢查每個英文字母的數量是不是皆為 k 的倍數
若有任何一個英文字母數量不為 k 的倍數,他就無法被平分成 k 等分了
另外,要如何對「英文字母」做統計呢?
我們可以把 'a' 的數量存在第 0 格
'b' 存在第 1 格, ..., 'z' 存在第 25 格, 以此類推
這樣就能用長度為 26 格的陣列來計數了!
對於任意小寫英文字母
我們只要算出他在字元表裡離 'a' 有多遠
就可以得知他應該存在第幾格
這就是將英文字母轉換成數字的小技巧
```cpp=
// 長度為 26 格的陣列,每格歸零
int count[26] = {0};
// 拜訪 words 裡面的每個字串
for(int i=0;i<words.size();i++){
// 拜訪字串裡的每個字元
for(int j=0;j<words[i].length();j++){
// 把這個字元減去 'a' 即可得知他的數量要存在哪一格
// 把那一格 +1
count[words[i][j]-'a']++;
}
}
// 檢查這 26 個字母,大家的數量都是 words.size() 的倍數嗎?
for(int i=0;i<26;i++){
// 若有一個字母的數量不是 words.size() 的倍數,即無法平分
if(count[i]%words.size()!=0) return false;
}
// 大家都可被 words.size() 整除,代表可以平分!
return true;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2206: 數字分成兩堆 ](https://leetcode.com/problems/divide-array-into-equal-pairs/)
>
> 題目給一個名為 nums 的陣列,請問能不能把裡面的數字均分成兩組呢?
這一題不需要處理字元,只是一般的數字,範圍為 1 至 500
計算完數量後,只需要檢查大家的數量是否皆為 2 的倍數即可
<font color='darkorange'>【例題】</font>
> 題目給一個名為 deck 的陣列,裡面有一些數字
> 請問是否能夠把這些數字均分成多個組呢?
> 也就是說,是否存在一個數字 x (大於1)能讓我們把 deck 裡的數字均分成 x 組呢?
這是 Leetcode 上的題目,連結是 [Leetcode 914](https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/)
我們要做的就是統計每個數字的數量,並算出大家的最大公因數是否大於 1
計算公因數可以使用 c++ 的內建函數 gcd
- 計算 a, b 兩數的最大公因數可以呼叫 gcd(a, b)
- 計算 a, b, c 三數的最大公因數可以先取 a 和 b 的最大公因數,再和 c 取最大公因數,也就是 gcd(gcd(a, b), c)
- 計算某個陣列 `arr` 裡面每個數字的最大公因數,可以寫成
- `g = arr[0];`
- `for(int i=1;i<arr.size();i++) { g = gcd(g, arr[i]);}`
- 最後 `g` 就是整個陣列 `arr` 的最大公因數
應用到這題如下所示:
```cpp=
// 先完成計數
int count[10001] = {0};
for(int i=0;i<deck.size();i++){
count[deck[i]]++;
}
// 計算大家數量的公因數
// 先把最大公因數 greated_common_divider 初始化為 deck 裡任一數字的數量
int greated_common_divider = count[deck[0]];
for(int n=0;n<10000;n++){ // 拜訪每個數量
if(count[n]==0) continue; // 跳過數量為 0 的
// 用此數的數量來更新「目前的最大公因數」
greated_common_divider = gcd(greated_common_divider, count[n]);
}
// 若最大公因數大於 1 則答案為 true,否則為 false
return greated_common_divider>1;
```
### <font color='#0047AB'>配對問題</font>
<font color='darkorange'>【例題】</font>
> 題目給一個字串 s
> 請問從 s 裡面取若干個字元能夠組成的最長回文可以是多長?
> 舉例來說,s="abccccdd"
> 我們可以取一個 a,四個 c,兩個 d,拼成 "dccaccd",因此答案為 7
這是 Leetcode 上的題目,連結是 [Leetcode 409](https://leetcode.com/problems/longest-palindrome/)
回文就是前後對稱的字串,像是 ABCBA 或是 ABBA
第一個字母等於最後一個字母,第二個字母等於倒數第二個字母...兩兩配對以此類推
因此要盡可能從 s 裡取走很多的「對子」
例如:若 A 有 5 個,我們就取走 4 個 A;若 B 有 6 個,我們就把 6 個 B 都取走...
如果取完所有對子還有剩下的(例如 5 個 A 取走 4 個剩下一個)
就取一個來放在回文的正中間,它不需跟其他字母配對(像是 ABCBA 的 C)
這一題的英文字母有大寫也有小寫,總共有 52 種可能,稍微麻煩一點
```cpp=
// 用 52 格的陣列來計數
int count[52] = {0};
for(int i=0;i<s.length();i++){
// 如果是小寫,就放在第 0 至 25 格
if('a'<=s[i] && s[i]<='z') count[s[i]-'a']++;
// 如果是大寫,就放在第 26 至 51 格
else count[s[i]-'A'+26]++;
}
```
接下來計算「可以組成幾個對子」和「剩下幾個孤隻」
也就是「除以二的商是幾」,「餘數是幾」
```cpp=9
int num_of_pairs = 0; // 計算有幾個對子
int num_of_singles = 0; // 計算剩幾個孤隻
for(int i=0;i<52;i++){ // 拜訪這 52 個英文字母
num_of_pairs += count[i]/2;
num_of_singles += count[i]%2;
}
```
最後取可以做成回文的材料
```cpp=15
int ans = num_of_pairs*2; // 對子全部拿來使用
if(num_of_singles>0) ans++; // 若有孤隻,就拿一個
return ans;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2341: 配對與剩餘的孤隻 ](https://leetcode.com/problems/maximum-number-of-pairs-in-array/)
>
> 題目給一個名為 nums 的陣列,請問可以把裡面的數字配成幾對?剩下幾個孤隻?
這一題也只要用數字計數就好,不需處理字元
最後要回傳的是一維 vector,第 0 格放「有幾個對子」,第 1 格放「剩幾個孤隻」
## <font color='darkblue'>適用題型:成員比對問題</font>
### <font color='#0047AB'>兩組成員是否相同</font>
<font color='darkorange'>【例題】</font>
> 題目給兩個字串 s 和 t
> 請問兩者的字元組成是相同的嗎?
> 例如 "anagram" 和 "nagaram" 就是相同的
> 因為兩者都有三個 a,一個 g, 一個 m, 一個 n 和一個 r
這是 Leetcode 上的題目,連結是 [Leetcode 242](https://leetcode.com/problems/valid-anagram/)
我們要對於兩者的字元分別計數,再比對是否「每個字元在兩字串出現的次數皆相同」
```cpp=
if(s.length()!=t.length()) return false; // 如果長度不同,當然不可能成員一樣
// 我們已經非常熟悉的計數部分
int s_counter[26]={0};
int t_counter[26]={0};
for(int i=0;i<s.size();i++){
s_counter[s[i]-'a']++;
t_counter[t[i]-'a']++;
}
// 檢查每個英文字母,在 s 和 t 出現的次數是一樣的嗎?
for(int i=0;i<26;i++){
if(s_counter[i]!=t_counter[i]) return false; // 只要有一個不一樣就是 false
}
return true; // 已確認完大家都一樣
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 1460: 兩陣列的成員是否相同 ](https://leetcode.com/problems/make-two-arrays-equal-by-reversing-subarrays/)
>
> 題目給兩個陣列 target 和 arr,裡面各自有若干個數字
> 請問 target 和 arr 裡的數字成員組成是相同的嗎?
> 例如 target = [1,2,3,3], arr = [2,3,1,3] 就是相同的
> target = [1,2,3,3], arr = [1,2,3,1] 就是不同的
和例題的解法相同,但這題是數字,不需要處理英文字母
請注意數字的範圍為 1 至 1000,因此需要 1001 格的陣列來計數
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 389: 多了哪個字元? ](https://leetcode.com/problems/find-the-difference/)
>
> 題目給兩個字串 s 和 t
> t 比 s 多了一個字元,其餘組成成員完全相同
> 請找出 t 比 s 多出的那個字元
和例題一樣,先計數,且要處理英文字母對數字的轉換(字母減去 'a')
然後找出唯一在 t 裡比在 s 裡面多出現一次的字母即可
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 2068: 相差不大於 3 ](https://leetcode.com/problems/check-whether-two-strings-are-almost-equivalent/)
>
> 題目給兩個字串 word1 和 word2
> 請問是不是每個英文字母「出現在 word1 裡的次數」和「出現在 word2 裡的次數」
> 相差都不大於 3 呢?
先計數,且要處理英文字母對數字的轉換(字母減去 'a')
然後檢查是不是 26 個字母都是「兩個次數相減小於等於 3 且大於等於 -3」
### <font color='#0047AB'>材料是否夠用來組成目標</font>
<font color='darkorange'>【例題】</font>
> 題目給兩個字串 ransomNote 和 magazine
> 請問我們能夠從 magazine 裡取若干個字元重新排列組成 ransomNote 嗎?
這是 Leetcode 上的題目,連結是 [Leetcode 383](https://leetcode.com/problems/ransom-note/)
先分別統計 ransomNote 和 magazine 的成員
如果每個英文字母在 ransomNote 裡出現的次數都不超過在 magazine 裡出現的次數,就可以
```cpp=
// 熟悉的計數部分
int r_count[26] = {0};
int m_count[26] = {0};
for(int i=0;i<ransomNote.size();i++){
r_count[ransomNote[i]-'a']++;
}
for(int i=0;i<magazine.size();i++){
m_count[magazine[i]-'a']++;
}
// 檢查 26 個英文字母
for(int i=0;i<26;i++){
// 如果 ransomNote 需要的比 magazine 提供的多,則不可
if(r_count[i]>m_count[i]) return false;
}
// 已確認完每個字母都夠給 ransomNote 用
return true;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 1160: 哪些字串夠被組出來 ](https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/)
>
> 題目給一個陣列 words 裡面有一些字串(相當於一些 ransomNote)
> 還有一個字串 chars(相當於 magazine)
> 請問 words 裡面的哪些字串是能夠從 chars 裡取一些字元組合成的呢?
> 請將符合條件的這些字串長度加總並回傳
這一題可以拿 words 裡面的每一個字串 words[i] 來呼叫例題的函數
`canConstruct(words[i], chars)` 來幫助判斷「可以或不可以組成」
若可以,就將 words[i] 的長度加總到答案上
### <font color='#0047AB'>材料可以組成幾組目標</font>
<font color='darkorange'>【例題】</font>
> 題目給兩個字串 s 和 target
> 我們可以從 s 裡取若干個字母重新排列組成 target,且取過的字母不可重複利用
> 請問可以組成幾個 target?
> 例如 s = "ilovecodingonleetcode", target = "code"
> 則答案為 2,因為我們可以從 s 中汲取兩次 "code" 出來
這是 Leetcode 上的題目,連結是 [Leetcode 2287](https://leetcode.com/problems/rearrange-characters-to-make-target-string/)
若 s 可以拼成 X 個 target,代表每個字母在 s 裡出現的次數都是在 target 裡的 X 倍或更多
反過來說
我們可以統計每個字母「在 s 裡出現的次數」是「在 target 裡出現的次數」的幾倍
再取 26 個字母裡的最小值即可
```cpp=
// 計數
int s_count[26] = {0};
int t_count[26] = {0};
for(int i=0;i<s.length();i++){
s_count[s[i]-'a']++;
}
for(int i=0;i<target.length();i++){
t_count[target[i]-'a']++;
}
int ans = s.length(); // 要算出所有倍數的最小值,先初始化成一個很大的值
for(int i=0;i<26;i++){
if(t_count[i]==0) continue; // 如果此字母根本沒出現在 target 裡,就跳過他
ans = min(ans, s_count[i]/t_count[i]); // 算倍數,並更新最小值
}
return ans;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 1189: 夠組成幾個"balloon" ](https://leetcode.com/problems/maximum-number-of-balloons/)
>
> 題目給一個字串 text,請問以他為材料可以拼成幾個 "balloon"?
和例題類似,例題的 s 是這題的 text,例題的 target 是這題的 "balloon"
### <font color='#0047AB'>成員的交集</font>
<font color='darkorange'>【例題】</font>
> 題目給若干個字串,請找出這些字串共有的字元(複數個的也要算入)
> 例如 ["bella","label","roller"] 大家都有一個 e 兩個 l,所以答案是 ["e", "l", "l"]
> 例如 ["cool","lock","cook"] 的答案就是 ["c", "o"],雖然 cool 和 cook 都有兩個 o,但因為 lock 只有一個 o,所以 o 在三者的共通點裡就只有一個
這是 Leetcode 上的題目,連結是 [Leetcode 1002](https://leetcode.com/problems/find-common-characters/)
首先是計數的部分
因為有多個字串,所以我們要用多個長度為 26 的陣列來計數
我們可以用尺寸為 (26, n) 的二維陣列(n 是字串的數量)來計數
```cpp=
// count[字母][編號] 存的是某字母在第某號的字串裡出現的次數
// 例如 count[0][5] 代表字母 'a' 在第 5 個字串裡出現的次數
vector<vector<int>> count(26, vector<int>(words.size(), 0));
for(int i=0;i<words.size();i++){
for(int j=0;j<words[i].length();j++){
count[words[i][j]-'a'][i]++;
}
}
```
接著是共通點的部分
舉例來說,字母 a 在三個字串裡出現的次數分別為 5, 8, 4,那麼這三個字串的共通點就只有 4 個 a,因為 4 是 [5, 8, 4] 的最小值
也就是說,對於每個字母,我們都要找它在每個字串出現的次數的最小值,才可知最後答案要出現幾次這個字母
```cpp=9
vector<string> ret;
for(int i=0;i<26;i++){ // 對於每個字母
int min_count = count[i][0];
for(int j=0;j<words.size();j++){ // 找出它在每個字串出現次數的最小值
min_count = min(min_count, count[i][j]);
}
for(int j=0;j<min_count;j++){ // 於是這個字母要在答案裡重複 min_count 次
ret.push_back(string(1, 'a'+i)); // 不知道為何題目要回傳字串,在此處理一下
}
}
return ret;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 350: 兩個陣列的交集 ](https://leetcode.com/problems/intersection-of-two-arrays-ii/)
>
> 題目給兩個整數陣列,請找出這兩個陣列共有的數字(複數個的也要算入)
這題只有兩個陣列,且不需處理字元!
## <font color='darkblue'>用陣列無法處理的情況</font>
在正式開始介紹 unordered_map 這個資料結構前
我們竟然已經光靠著陣列就解了 20 幾道計數問題
可見陣列用途真的很廣泛
但因為還是有不少「陣列無法處理」或「用陣列處理就會不太理想」的例子
讓我們一起來認識這些例子
並且學習如何使用 unordered_map 來解題
### <font color='#0047AB'>數字範圍太廣,浪費陣列空間</font>
假設有一個題目,給一個陣列,裡面有 1000 個數字
這些數字的範圍是 1 到 1000000000
若題目要我們找出「出現了最多次的數字」
我們是不是就需要一個長度為 1000000000 的陣列來計數了呢
但明明題目裡只有 1000 個數字,代表我們最多只會用到 1000 個格子
剩下 999999000 個格子都浪費了
這樣的程式不只浪費記憶體,也會浪費時間(因為我們要看遍這1000000000格去找最大值)
```cpp=
int count[1000000000] = {0}; // 用了 1000000000 格記數
for(int i=0;i<1000;i++){ // 題目其實只有 1000 個數字,只是數字的值的範圍很大而已
count[nums[1000]]++;
}
int ans = 0;
for(int i=0;i<1000000000;i++){ // 迴圈要跑 1000000000 才能找最大值
ans = max(ans, count[i]);
}
return ans;
```
### <font color='#0047AB'>千奇百怪的資料型態</font>
假設有一個題目,給一個陣列,裡面有 1000 個數字
這些數字的範圍都是 -1000000000 到 1000000000,要找出現最多次的數字
這就更慘了,先不論浪費記憶體的問題
負數根本沒有對應的格子可以存(因為陣列的編號是0和正整數)
或是有一個題目,給一個陣列,裡面有 1000 個「字串」
要找出現最多次的「字串」,這就完全沒辦法用陣列來計數了
從下一章開始,我們會介紹如何使用 unordered_map 來處理這些問題!