BiruLyu
6/6/2017 - 6:37 PM

## 406. Queue Reconstruction by Height(in place).java

``````/*

public class Solution {
public int[][] reconstructQueue(int[][] people) {
if( people == null || people.length < 2 || people[0].length < 2) return people;

Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if(b[0] == a[0]) return a[1] - b[1];
return b[0] - a[0];
}
});

ArrayList<int[]> temp = new ArrayList<int[]>();
int len = people.length;
for(int i = 0; i < len; i++) {
}

int[][] res = new int[len][2];
for(int i = 0; i < len; i++){
res[i][0] = temp.get(i)[0];
res[i][1] = temp.get(i)[1];
}
return res;
}
}``````
``````class Solution {
public:
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
sort(people.begin(), people.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return a.first > b.first || (a.first == b.first && a.second < b.second);
});
for (int i = 1; i < people.size(); ++i) {
int cnt = 0;
for (int j = 0; j < i; ++j) {
if (cnt == people[i].second) {
pair<int, int> t = people[i];
for (int k = i - 1; k >= j; --k) {
people[k + 1] = people[k];
}
people[j] = t;
break;
}
if (people[j].first >= people[i].first) ++cnt;
}
}
return people;
}
};``````