Сложность: medium
Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания.
Реализуйте класс Solution:
Solution(int[] nums): Инициализирует объект целочисленным массивом nums.
int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его.
int[] shuffle(): Возвращает случайное перемешивание массива.
Пример:
Input: ransomNote = "a", magazine = "b"
Output: false
👨💻 Алгоритм:
1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива.
2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент.
3⃣Один небольшой, но важный момент заключается в том, что возможно поменять элемент сам с собой - в противном случае некоторые перестановки массива были бы более вероятны, чем другие.
😎 Решение:
class Solution {
private var array: [Int]
private let original: [Int]
init(_ nums: [Int]) {
self.array = nums
self.original = nums
}
func reset() -> [Int] {
self.array = self.original
return self.original
}
func shuffle() -> [Int] {
for i in 0..<array.count {
let randIndex = Int.random(in: i..<array.count)
array.swapAt(i, randIndex)
}
return array
}
}Ставь 👍 и забирай 📚 Базу знаний