406. Queue Reconstruction by Height (신장 에 따라 대열 재건) 중등 난이도

1810 단어 leetcode
순 서 를 어 지 럽 히 는 한 무리의 사람들 이 대열 에 서 있다 고 가정 하 다.모든 사람 은 하나의 정수 대 4. 567914 로 그 중에서 4. 567914. 이 사람의 키 이 고 4. 567914. 이 사람 앞 에 있 으 며 키 가 4. 567914 보다 크 거나 같은 사람 이다.이 대기 열 을 다시 만 들 기 위해 알고리즘 을 만 듭 니 다.
주의: 총 인원 이 1100 명 보다 적 습 니 다.
예시
  :
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

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

이 문 제 는 제 가 여러 가지 방법 을 생각 했 습 니 다. 예 를 들 어 하나씩 정렬 (정렬 선택) 하 는 것 을 포함 합 니 다. 그러나 큰 문 제 는 바로 이런 정렬 이 첫 번 째 만 요구 에 부합 되 고 뒤의 것 은 요구 에 부합 되 지 않 을 수 있 습 니 다.
그래서 저 는 AC 를 본 후에 야 비교적 편리 한 방법 이 생각 났 습 니 다. 먼저 정렬 을 하고 큰 것 부터 작은 것 까지 세 는 상황 에서 K 값 이 큰 것 이 뒤에 있 습 니 다.왜?K 값 을 고려 했 기 때문에 큰 것 부터 작은 것 까지 정렬 하면 가장 큰 수의 K 값 의 위 치 는 그들 이 처 한 위치 이기 때문이다.
그 다음 에 이 배열 에서 두 번 째 정렬 을 하고 순 서 는 그들의 K 값, 예 를 들 어 K = 0 에 따라 첫 번 째 로 삽입 합 니 다.
class Solution {
public:
 bool paixu (pair a , pair b){
        if(a.first == b.first ) return a.second < b.second ;
        return a.first > b.first ;
    }
    vector> reconstructQueue(vector>& people) {
        sort(people.begin(),people.end(),paixu);
        });//    ,            (               ,         )  ,      ,    k       。
/*sort        :
 sort(people.begin(),people.end(),[](const pair &a,const pair &b){//            
            return a.first > b.first || (a.first == b.first && a.second < b.second);
        });
*/
        vector> res(people.size());
        for(int i = 0;i < people.size();i++)
        {
            ////                   k          
            res.insert(res.begin()+people[i].second , people[i]);
        }
        res.resize(people.size());  //    (size); 
        return res;
    }
};

좋은 웹페이지 즐겨찾기