Сложность: medium
Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива.
Пример:
Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.
👨💻 Алгоритм:
1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.
2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones.
3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].
😎 Решение
class Solution {
func minSwaps(_ data: [Int]) -> Int {
let ones = data.reduce(0, +)
var cnt_one = 0, max_one = 0
var left = 0, right = 0
while right < data.count {
cnt_one += data[right]
right += 1
if right - left > ones {
cnt_one -= data[left]
left += 1
}
max_one = max(max_one, cnt_one)
}
return ones - max_one
}
}Ставь 👍 и забирай 📚 Базу знаний