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;
    }
};