【leetcode】 406 Queue Reconstruction by Height

发表于

描述
给定一些数字，要求重新排序

1
2
3
4
5
input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

每一组数据有两个数字组成，要求每组数据第二个数据为排在它前面大于等于它的数字的个数。
比如[5,2]在它前面有两个数据都大于等于它。

初始数据[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

思路

  1. 找出最大的数，再对它根据第二个数排序，得到[[7,0],[7,1]]
  2. 找出第二大的数，同样的排序，得到[6,1]
  3. 将[6,1]插入，得到[[7,0],[6,1],[7,1]]
  4. 找出第三大数，[[5,0],[5,1]]插入得到[[5,0],[5,1],[7,0],[6,1],[7,1]]
  5. 找出第四大数，[4,4],插入得到[[5,0],[5,1],[7,0],[6,1],[4,1],[7,1]]
  6. DONE。

vector没有自带的find(),set和map有
map<int,vector<int>>后面的不会自动排序，而改成map<int,set<int>>可以排序
markdowm中的<和>需要转义，利用&it;和&gt;
map插入数据mymap.insert({1,1}),加入大括号，或者mymap.insert(std::pair<int,int>(1,1))

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        map <int, set<int>> peo;
        for (int i = 0; i < people.size(); i++) {
            auto p = people[i];
            peo[p.first].insert(p.second);
        }
        vector<pair<int, int>> result;
        for (auto iter = peo.rbegin(); iter!= peo.rend(); iter++) {
            for (auto iter2 = iter->second.begin(); iter2 != iter->second.end(); iter2++) {
                result.insert(result.begin() + *iter2, { iter->first,{*iter2} });
            }
        }
        return result;
    }
};

值得学习的代码
原文链接

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        auto comp = [](const pair<int, int>& p1, const pair<int, int>& p2)
        { return p1.first == p2.first ? p1.second < p2.second : p1.first > p2.first; };
        sort(people.begin(), people.end(), comp);
        vector<pair<int, int>> res;
        for (auto& p : people) {
            res.insert(res.begin() + p.second, p);
        }
        return res;
    }
};

参考资料
原题链接