Multi-keyword Sort 多關鍵字排序

問題描述：

給定 

n

 個學生的學号(從 

1

 到 

n

 編号)以及他們的考試成績，表示為(學号，考試成績)，請将這些學生按考試成績降序排序，若考試成績相同，則按學号升序排序。

樣例1：

輸入: array = [[2,50],[1,50],[3,100]]

輸出: [[3,100],[1,50],[2,50]]

樣例2：

輸入：[[7,66],[4,77],[3,63],[5,81],[1,88],[9,86],[6,88],[2,82],[8,55],[10,95]]

輸出：[[10,95],[1,88],[6,88],[9,86],[2,82],[5,81],[4,77],[7,66],[3,63],[8,55]]

思路：使用C++自帶的map、vector容器類型。其中map存放{key, value}對，key為考試成績，value為學号清單（考試成績同為某個key的所有學生學号）；利用map的自動排序功能，保持考試成績按從大到小排列。而學号清單因為是可變長度的，是以使用vector類型，利用vector的自動排序函數，将學号清單從小到大排列。

代碼如下：

class Solution {
public:
    /**
     * @param array: the input array
     * @return: the sorted array
     */
    vector<vector<int>> multiSort(vector<vector<int>> &array) {
        // Write your code here
        vector<vector<int>> res;
        map<int,vector<int>,greater<int>> m;
        map<int,vector<int>,greater<int>>::iterator iter;
    
        for (int i = 0; i < array.size(); i++) {
            iter = m.find(array[i][1]);
            if(iter!=m.end()) {
                vector<int> t = m[array[i][1]];
                t.push_back(array[i][0]);    
                m[array[i][1]] = t;        
            } else {
                vector<int> t = {array[i][0]};
                m.insert(make_pair(array[i][1], t));
            }
        }
        iter = m.begin();
        while(iter!=m.end()) {
            //cout<<"key: "<<iter->first<<endl;
            vector<int> s = iter->second;
            sort(s.begin(),s.end());
            if (s.size()>1) {
                //cout<<"value: "<<endl;
                for (int ii = 0; ii < s.size(); ii++) {
                    res.push_back({s[ii],iter->first});
                    //cout<<" "<<s[ii]<<" ";
                }
                //cout<<endl;
            } else {
                //cout<<"value: "<<s[0]<<endl;
                res.push_back({s[0],iter->first});
            }
            iter++;
        }
        return res;
    }
};