LeetCode 406. 根据身高重建队列

Categories:

题目描述
思路分析
1. 解法一：排序 + 插入（推荐）
相似题目

题目描述

✅ 406. 根据身高重建队列

思路分析

解法一：排序 + 插入（推荐）

核心思路：

按身高降序、k 升序排序。

依次插入到结果列表的第 k 个位置，保证前面正好有 k 个不矮于他的人。

排序后插入即可得到唯一队列。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示人数，插入主导。

空间复杂度：O(n)，用于结果列表。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> {
            if (a[0] != b[0]) {
                return b[0] - a[0];
            }
            return a[1] - b[1];
        });

        List<int[]> res = new ArrayList<>();
        for (int[] person : people) {
            res.add(person[1], person);
        }

        return res.toArray(new int[people.length][2]);
    }
}

import "sort"

func reconstructQueue(people [][]int) [][]int {
	sort.Slice(people, func(i, j int) bool {
		if people[i][0] != people[j][0] {
			return people[i][0] > people[j][0]
		}
		return people[i][1] < people[j][1]
	})

	res := make([][]int, 0)
	for _, p := range people {
		idx := p[1]
		res = append(res, nil)
		copy(res[idx+1:], res[idx:])
		res[idx] = p
	}

	return res
}

相似题目

题目	难度	考察点
56. 合并区间	中等	排序
435. 无重叠区间	中等	贪心
452. 用最少数量的箭引爆气球	中等	排序
646. 最长数对链	中等	排序
1029. 两地调度	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/74178578