Постановка задачи. Дан массив двоичных цифр, 0 и 1, отсортируйте массив так, чтобы все нули были на одном конце, а все единицы — на другом.
Какой конец не имеет значения . Чтобы отсортировать массив, поменяйте местами любые два соседних элемента. Определите минимальное количество перестановок для сортировки массива.

Пример: обр = [0,1,0,1] вывод = 1

переключение элементов 1 и 2 дает [0,0,1,1] отсортированный массив.

Пример: arr = [1,1,1,1,0,1,0,1] output = 3 , [1,1,1,1,1,0,0,1] →[1,1,1, 1,1,0,1,0] →[1,1,1,1,1,1,0,0]

Теперь, когда вы ясно понимаете вопрос, давайте сосредоточимся на ограничениях проблемы. Здесь наиболее важно сосредоточиться на том, что постановка задачи позволяет вам поменять местами только любые два смежных элемента. И нам нужно вернуть минимальные свопы, необходимые для сортировки arr в любом порядке, это единственное ограничение, о котором нужно позаботиться.

И важное наблюдение здесь заключается в том, что нам не нужно сортировать массив, а вместо этого возвращать минимальные свопы, необходимые для сортировки массива в любом порядке.

Есть два подхода к этому решению.

Подход 1:

В тот момент, когда я увидел, что в задаче можно поменять местами только соседние элементы и ключевое слово SORT, я подумал об алгоритмах сортировки. Первый алгоритм, который пришел мне на ум, — Сортировка вставками. Используя сортировку вставками, вы можете выбрать элемент и поместить его в правильное положение по направлению к левому краю. Но задача здесь состоит в том, чтобы подумать о том, как сравнивать элементы и в каком порядке сортировать массив, чтобы получить минимальные свопы для сортировки в любом порядке.

Во-первых, нам нужно отсортировать массив по возрастанию и определить общее количество свопов, выполненных алгоритмом, и сохранить его в переменной, т.е. "a", а затем сделать то же самое, чтобы отсортировать массив по убыванию. и определить общее количество свопов и сохранить в переменной, т.е. "d".

Теперь, когда вы определили количество перестановок для сортировки массива как по возрастанию, так и по убыванию, вам просто нужно вернуть минимум из значений переменных "a" и "d".

Временная сложность: O(N²) , Пространственная сложность: O(1)

Подход 2:

Как мы обсуждали ранее, нам не обязательно сортировать массив, нам просто нужно определить минимальное количество свопов. Как только мы это поймем, следующее, что придет нам в голову, это «Могу ли я сделать что-то, используя подход с двумя указателями?». Ответ положительный.

Мы рассмотрим возможность использования двух указателей, то есть index_pointer и element_pointer. Изначально index_pointer указывает на 0-й индекс, а element_pointer указывает на первый элемент массива.

Мы начнем перебирать заданный массив с помощью обычного цикла for с 0-го индекса, и в тот момент, когда мы увидим, что element_pointer указывает на «0» в массиве, мы определим, сколько свопов нужно, чтобы поменять этот конкретный 0 на 0-й показатель. Мы можем сделать это, найдя разницу между abs(index_pointer — индекс, на который указывает element_pointer) и добавив ее в переменную total_counter. И теперь мы увеличиваем index_pointer на единицу, потому что в следующий раз, когда мы найдем «0», он должен быть помещен в 1-й индекс, поскольку 0-й индекс теперь считается заполненным элементом «0».

Как только наш цикл завершится, мы получим общее количество свопов, необходимых для сортировки массива в порядке возрастания без фактической сортировки массива.

Точно так же нам нужно выполнить указанную выше задачу, чтобы найти общее количество свопов, необходимых для сортировки массива в порядке убывания. Мы можем сделать то же самое, что обсуждалось выше, но теперь element_pointer должен указывать на единицу в итерации.

Как только мы найдем total_number свопов, необходимых для сортировки массива как по возрастанию, так и по убыванию без их фактической сортировки, мы можем просто найти минимум из этого и вернуть его.

Временная сложность: O(N), так как вам просто нужно выполнить итерацию массива, Пространственная сложность: O(1)

Ниже приведен фрагмент кода:

Надеюсь, вам понравилось читать! Ударь меня в ладоши, если тебе это нравится.

Удачного кодирования!