leetcode-queue-resconstruction-by-height

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/queue-reconstruction-by-height/

　　给了你n个pair，pair的一个值是人的高度，第二个是在当前位置前边身高不小于当前的人的个数，让你恢复这个pair数组，保证正确性

题目分析

　　贪心法，看了下discuss区的解答，思路是这样的：先将pair排序，规则是first值大者在前，如果first相同，那么second值小的在前，然后重新构建数组，可以借助一个辅助的数组理解思路，每次从原数组中拿出一个pair，将它插入到辅助数组中的pair.second的位置，不断拿出一直到最后。

　　第二种思路，不借助辅助数组，就是会需要不断手动移动元素保持数组。

代码

　　第一种思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    static bool mysort(pair<int, int>& a, pair<int, int>& b){
        return (a.first == b.first) ? (a.second < b.second) : (a.first > b.first);
    }
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int> >& people) {
        std::sort(people.begin(), people.end(), mysort);
        
        int len = people.size();
        for (int i = 1; i < len; i++) {
            int loc = people[i].second;
            if (loc == i) {
                continue;
            }
            int f = people[i].first;
            int s = people[i].second;
            for (int j = i - 1; j >= loc; j--) {
                people[j + 1].first = people[j].first;
                people[j + 1].second = people[j].second;
            }
            people[loc].first = f;
            people[loc].second = s;
            
        }
        return people;
    }
};

　　时间复杂度 O(n ^ 2)

　　第二种思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    static bool mysort(pair<int, int>& a, pair<int, int>& b){
        return (a.first == b.first) ? (a.second < b.second) : (a.first > b.first);
    }
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int> >& people) {
        std::sort(people.begin(), people.end(), mysort);
        vector<pair<int, int> > res;
        int len = people.size();
        for (vector<pair<int, int> >::iterator it = people.begin(); it != people.end(); it++) {
            res.insert(res.begin() + (*it).second, *it);
        }
        return res;
    }
};

　　时间复杂度 O(n ^ 2)