根据身高重建队列

全栈程序员站长

发布于 2021-04-07 11:25:44

2810

发布于 2021-04-07 11:25:44

文章被收录于专栏：全栈程序员必看

假设有打乱顺序的一群人站成一个队列。每个人由一个整数对 (h, k) 表示，其中 h 是这个人的身高，k 是排在这个人前面且身高大于或等于 h 的人数。编写一个算法来重建这个队列。

解题思路

先排序，再插入，排序的规则是：按照高度 h 降序，k 升序排序。再遍历排序后的数组，根据 k 将元素插入到 k 的位置上。核心思想是：高个子先站好位，矮个子插入到 k 位置上，前面肯定有 k 个高个子

class Solution {
    
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
        LinkedList<int[]> list = new LinkedList<>();
        for (int[] i : people) {
            list.add(i[1], i);
        }
        return list.toArray(new int[list.size()][2]);
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020年11月19日，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历