PHP | LeetCode

Задача: 506. Relative Ranks
Сложность: easy

Вам дан целочисленный массив score размером n, где score[i] — это результат i-го спортсмена на соревновании. Все результаты гарантированно уникальны.
Спортсмены размещаются на основе своих результатов: спортсмен, занявший 1-е место, имеет наивысший результат, спортсмен, занявший 2-е место, имеет второй по величине результат и так далее. Размещение каждого спортсмена определяет его ранг:
Ранг спортсмена, занявшего 1-е место, — "Gold Medal".
Ранг спортсмена, занявшего 2-е место, — "Silver Medal".
Ранг спортсмена, занявшего 3-е место, — "Bronze Medal".
Для спортсменов, занявших с 4-го по n-е место, их ранг соответствует их номеру в размещении (т.е. ранг спортсмена, занявшего x-е место, — "x").
Верните массив answer размером n, где answer[i] — это ранг i-го спортсмена.

Пример:

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

👨‍💻

Алгоритм:

1⃣

Инициализация и нахождение максимального значения
Инициализируйте переменную N длиной массива score. Определите функцию findMax, которая находит максимальный балл в массиве score.

2⃣

Создание вспомогательных структур
Инициализируйте массив scoreToIndex размером M + 1, где M — это максимальное значение в массиве score. Заполните scoreToIndex таким образом, чтобы для каждого score[i] его индекс сохранялся в scoreToIndex[score[i]].

3⃣

Присваивание рангов и формирование ответа
Создайте массив rank для хранения рангов спортсменов. Используйте цикл для присваивания медалей и рангов в зависимости от значений в scoreToIndex, начиная с наибольшего.

😎

Решение:

class Solution {
    function findRelativeRanks($score) {
        $N = count($score);
        $maxScore = max($score);
        $scoreToIndex = array_fill(0, $maxScore + 1, 0);
        
        foreach ($score as $i => $s) {
            $scoreToIndex[$s] = $i + 1;
        }
        
        $MEDALS = ["Gold Medal", "Silver Medal", "Bronze Medal"];
        $rank = array_fill(0, $N, "");
        $place = 1;
        
        for ($i = $maxScore; $i >= 0; $i--) {
            if ($scoreToIndex[$i] != 0) {
                $originalIndex = $scoreToIndex[$i] - 1;
                if ($place < 4) {
                    $rank[$originalIndex] = $MEDALS[$place - 1];
                } else {
                    $rank[$originalIndex] = strval($place);
                }
                $place++;
            }
        }
        
        return $rank;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post