个人中心
gpt4 book ai didi

406. Queue Reconstruction by Height 根据身高重建队列

转载 作者：大佬之路 更新时间：2024-01-31 14:17:48 25 4
gpt4 key购买 nike

题目地址：https://leetcode.com/problems/queue-reconstruction-by-height/#/descriptionopen in new window

题目描述

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note: The number of people is less than 1,100.

Example：

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

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

题目大意

给出了一个数组，数组的每个元素表示一个人的身高以及在一个队伍前面不比他矮的人的个数。现在要重新排列，使得数组是满足条件的。

解题方法

这个题怎么想出来的呢？是因为我们考虑如果先把个子高的排好序，那么在任何位置插入数据都不会对已经排好序的数组造成影响。而，与此同时，我们已经知道了个子高的排序，那么当新的数据到的时候，我们要确定它的位置也很简单，因为现在的所有数据都比他高，所以只要根据他的第二个数字确定他的位置即可。

先对已有的数组进行排序。按照高度降序排列，如果高度一样，按照k的值升序排列。这样比如一开始[7，0] [7，1] [7，2]就会排好，然后比如说后面有一个[6，1]， 说明只有一个大于或等于它，又因为比6大的已经全部取出。所以把它放在位置1，这样就变成[7，0] [6，1] [7，1] [7，2].然后比如又有一个[5，0].就放在位置0，以此类推。

即对于案列。首先排序成：

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

然后对于第二个数字进行插入对应位置：

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

Python代码如下：

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        people.sort(key = lambda x : (-x[0], x[1]))
        res = []
        for p in people:
            res.insert(p[1], p)
        return res

1 2 3 4 5 6 7 8 9 10 11

C++代码如下，需要注意自定义sort()函数的比较方法。

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);
        });
        vector<pair<int, int>> res;
        for (auto p : people) {
            res.insert(res.begin() + p.second, p);
        }
        return res;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13

Java代码如下，之前写的，有点冗长了。

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
		if (people == null || people.length == 0) {
			return people;
		}
		Arrays.sort(people, new Comparator<int[]>() {
			@Override
			public int compare(int[] p1, int[] p2) {
				return p1[0] == p2[0] ? p1[1] - p2[1] : p2[0] - p1[0];
			}
		});
		List<int[]> temp = new ArrayList<int[]>();
		for (int[] aPeople : people) {
			if (people.length == aPeople[1]) {
				temp.add(aPeople);
			} else {
				temp.add(aPeople[1], aPeople);
			}
		}
		int ans[][] = new int[people.length][2];
		for (int i = 0; i < temp.size(); i++) {
			ans[i] = temp.get(i);
		}
		return ans;
    }
}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发

25 4 0
文章推荐： 409. Longest Palindrome 最长回文串
文章推荐： 723. Candy Crush 粉碎糖果
文章推荐： 718. Maximum Length of Repeated Subarray 最长重复子数组
文章推荐： 445. Add Two Numbers II 两数相加 II
大佬之路
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com