Python | LeetCode
Задача: 384. Shuffle an Array
Сложность: medium
Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания.
Реализуйте класс Solution:
Solution(int[] nums): Инициализирует объект целочисленным массивом nums.
int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его.
int[] shuffle(): Возвращает случайное перемешивание массива.
Пример:
Input: ransomNote = "a", magazine = "b"
Output: false
👨💻 Алгоритм:
1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива.
2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент.
3⃣Один небольшой, но важный момент заключается в том, что возможно поменять элемент сам с собой - в противном случае некоторые перестановки массива были бы более вероятны, чем другие.
😎 Решение:
import random
class Solution:
def __init__(self, nums: list[int]):
self.array = nums[:]
self.original = nums[:]
def reset(self) -> list[int]:
self.array = self.original[:]
return self.original
def shuffle(self) -> list[int]:
for i in range(len(self.array)):
rand_index = random.randint(i, len(self.array) - 1)
self.array[i], self.array[rand_index] = self.array[rand_index], self.array[i]
return self.array
Ставь 👍 и забирай 📚 Базу знаний
5 · 596 ·