07 多重集合

332 重新安排行程 (opens new window)

给定一个人坐过的一些飞机的起止机场，已知这个人从 JFK 起飞，那么这个人是按什么顺序飞的；如果存在多种可能性，返回字母序最小的那种。

输入是一个二维字符串数组，表示多个起止机场对子；输出是一个一维字符串数组，表示飞行顺序。

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] 输出：["JFK","ATL","JFK","SFO","ATL","SFO"] 解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

解析：

​ 本题可以使用哈希表记录机票的起飞机场和落地机场，由于可能存在多个不同落地机场，所以需要使用集合来存储。又由于可能存在重复路线，所以要保存落地机场的重复值，且要求结果的返回顺序是按照最小字母序，刚好可以使用多重集合 multiset，不仅可以存储重复值，而且多重集合的默认元素保存顺序是递增的，例如"SFO","ATL","JFK" 在多重集合中的保存顺序是 "ATL","JFK","SFO"。上例子的哈希表保存结果为：

Hash_key	Hash_value
JFK	{ATL, SFO}
SFO	{ATL}
ATL	{JFK, SFO}

​ 保存好起飞机场和落地机场的关系后，我们使用栈来恢复一条完整的从最终落地机场到达起始机场的路线。从起始机场开始，按照转移顺序将机场逐个压入栈。取当前栈顶作为下一个落地机场，如果栈顶为空则说明到达一个终点，将其加入结果。如果不为空，则将其作为起飞机场对应的第一个落地机场入栈并移除。完成上述过程就恢复出了一条从终点到起点的飞行路线。上例恢复的路线为JFK->ATL->JFK->SFO->ATL->SFO

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        // 构建哈希表多重集合，保存起飞机场对应的落地机场
        unordered_map<string, multiset<string>> hash;
        for(const auto ticket: tickets){
            hash[ticket[0]].insert(ticket[1]);
        }
        // 使用栈恢复从终点到达起点的逆向路线
        vector<string> ans;
        stack<string> st;
        st.push("JFK");
        while(!st.empty()){
            string end = st.top();
            // 当前机场对应的落地机场为空，说明他是一个终点
            if(hash[end].empty()){
                ans.push_back(end);
                st.pop();
            }else{
                st.push(*hash[end].begin());
                hash[end].erase(hash[end].begin());
            }
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};