Map

可以儲存 key 以及其對應 value 的容器，內部會按照 key 的值進行排序，有以下幾個常見的操作：

  • insert 加入元素
  • erase 刪除元素
  • count 確認該元素是否存在
  • find 回傳元素位置
  • empty 確認是否為空
  • size 回傳元素個數
  • clear 清空所有元素

Unordered Map

可以儲存 key 以及其對應 value 的容器，內部不會進行排序，而是使用雜湊表的方式進行一對一的對應，利於查詢對應元素的關係，可以使用的函數與 map 類似。

比較：

容器 map unordered_map
結構 紅黑樹 雜湊表
內部資料 有序 無序
查詢速度 較低 較高

通常在不要求內部元素有排序的情況下，會使用查詢效率較高的 unordered_map。

操作

遍歷

使用指針指向開頭，進行遍歷，使用 first 取 key、second 取 value。

1
2
3
4
for(auto i = m.begin(); i != m.end(); i++){
    cout << "key " << i -> first << endl;
    cout << "value " << i -> second << endl;
}

替代

在某些 key 值數量較少的情況下，例如 a ~ z 字母 或是 1 ~ 100 的數字，可以直接使用 vector 等容器，直接以索引值代表 key 並且儲存對應的 value。

練習

LeetCode 49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:
Input: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]
Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

Example 2:
Input: strs = [""]
Output: [[""]]

Example 3:
Input: strs = [“a”]
Output: [[“a”]]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        vector<vector<string>> ans;
        for(int i = 0; i < strs.size(); i++){
            string tmp(strs[i]);
            sort(tmp.begin(), tmp.end());
            if(m.count(tmp)) m[tmp].push_back(strs[i]);
            else m[tmp] = {strs[i]};
        }
        for(auto i = m.begin(); i != m.end(); i++){
            ans.push_back(i -> second);
        }
        return ans;
    }
};

利用同字母異序詞中字母經過排序之後會變為相同字串的特性，將其作為 key 值就可以將他們分組。

LeetCode 149. Max Points on a Line

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Return the max sliding window.

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        if(points.size() == 1) return 1;
        int ans = 0;
        for(int i = 0; i < points.size(); i++){
            unordered_map<double, int> m;
            for(int j = 0; j < points.size(); j++){
                if(i == j) continue;
                double k;
                if((points[i][0] - points[j][0])) k = (double)(points[i][1] - points[j][1]) / (double)(points[i][0] - points[j][0]);
                else k = 20001;
                if(m.count(k)) m[k]++;
                else m[k] = 1;
                ans = max(ans, m[k] + 1);
            }
        }
        return ans;
    }
};

使用雙重迴圈遍歷所有點，每次固定一個點，以他與其他點之間連線的斜率作為 key 值，value 儲存連線斜率相同的點數量，在判斷時要注意避免分母為 0 的情況。