Leetcode 406 根据身高重建队列

2023-12-22 12:34:37

题意理解

????????people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

? ? ? ? 给定一个二维数组,(h,k)h表示此人身高,k表示前面有几个人比他高。

? ? ? ? 我们按照每个人的h,k两个维度的需求给每个人排在合适的位置。

? ? ? ? 如:

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

????????

解题思路

? ? ? ?采用贪心思路来解题,明确全局最优和局部最优。

? ? ? ?全局最优:每个人的位置满足其h,k的需求。

? ? ? ?对于每个人的位置,我们需要考虑两个维度。

? ? ? ?对于需要考虑多个维度的题目,我们可以逐个考虑,减小难度。

? ? ? ?1.首先考虑k维度。我们将k从小到大排,k相同时,h从小到大排。

? ? ? ? 所以有:

? ? ? ? ? ? ? ? [5,0][7,0][6,1][7,1][5,2][4,4],其中[5,2],[4,4]位置错误

? ? ? ? 2.考虑h维度,将h从大到小排,h相同时,k从小到大排。

? ? ? ? 所以有:

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

? ? ? ? 我们发现:

? ? ? ? ? ? ? ? 身高高的总是在前面,当一个元素如[6,1]前面比它大的多的时候,需要将其往前移

? ? ? ? ? ? ? ? 因为前面每一个数都比他大,多以,一枝位置1处,其余后移即可。

????????????????其前面满足条件的并不会因为一个身高比他们都低的人加入,而不满足其位置条件。

? ? ? ? ? ? ? ? 依次类推:我们获得最终结果:

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

? ? ? ? 所以局部最优即:将身高最高的人,优先安排合理的位置

1.贪心解题

我们用result来记录结果。在处理问题之前,我们需要首先根据身高从大到小排序,身高相同时,根据k升序排序。

public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];   // a - b 是升序排列,故在a[0] == b[0]的狀況下,會根據k值升序排列
            return b[0] - a[0];   //b - a 是降序排列,在a[0] != b[0],的狀況會根據h值降序排列
        });
        LinkedList<int[]> result=new LinkedList<>();

        for(int i=0;i<people.length;i++){
            int position=people[i][1];
            result.add(position,people[i]);
        }
        //转数组
        return result.toArray(new int[people.length][]);
    }

2.分析?

时间复杂度:O(n^{2})? 排序所需时间O(nlogn)+遍历插入O(n^{2})

空间复杂度:O(nlogn) 排序所需的栈空间

n为输入数组长度。

文章来源:https://blog.csdn.net/lt_BeiMo/article/details/135147734
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。