406. Queue Reconstruction by Height

LeetCode medium оригинал: C# #array #csharp #leetcode #medium #queue #sort

LeetCode Static

Вам дан массив людей, people, которые являются атрибутами некоторых людей в очереди (не обязательно по порядку). Каждый people[i] = [hi, ki] представляет собой человека ростом hi, перед которым стоят ровно ki других людей, чей рост больше или равен hi. Реконструируйте и верните очередь, представленную входным массивом people. Возвращаемая очередь должна быть отформатирована как массив queue, где queue[j] = [hj, kj] - это атрибуты j-го человека в очереди (queue[0] - человек, находящийся в начале очереди).

Пример:

Input: people = [[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]]

C# решение

сопоставлено/оригинал

using System;
using System.Collections.Generic;
public class Solution {
    public int[][] ReconstructQueue(int[][] people) {
        Array.Sort(people, (a, b) => a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        List<int[]> result = new List<int[]>();
        foreach (var person in people) {
            result.Insert(person[1], person);
        }
        return result.ToArray();
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int[][] ReconstructQueue(int[][] people) {
        Array.Sort(people, (a, b) => a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        List<int[]> result = new List<int[]>();
        foreach (var person in people) {
            result.Insert(person[1], person);
        }
        return result.ToArray();
    }
}

Java решение

сопоставлено/оригинал

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

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        List<int[]> result = new ArrayList<>();
        for (int[] person : people) {
            result.add(person[1], person);
        }
        return result.toArray(new int[result.size()][]);
    }
}

JavaScript решение

сопоставлено/оригинал

function reconstructQueue(people) {
    people.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : b[0] - a[0]);
    const result = [];
    for (const person of people) {
        result.splice(person[1], 0, person);
    }
    return result;
}

Python решение

сопоставлено/оригинал

def reconstructQueue(people):
    people.sort(key=lambda x: (-x[0], x[1]))
    result = []
    for person in people:
        result.insert(person[1], person)
    return result

Go решение

сопоставлено/оригинал

package main

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][1] < people[j][1]
        }
        return people[i][0] > people[j][0]
    })
    result := [][]int{}
    for _, person := range people {
        result = append(result[:person[1]], append([][]int{person}, result[person[1]:]...)...)
    }
    return result
}

Algorithm

Отсортируйте массив people по убыванию роста hi. Если два человека имеют одинаковый рост, отсортируйте их по возрастанию значения ki.

Создайте пустой список для результата. Вставляйте каждого человека из отсортированного массива в список на позицию, соответствующую значению ki.

Верните список результата.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.