对给定二进制数组排序所需的最小相邻交换次数

---

我们可以使用不同的方法来最小化对相邻元素进行排序所需的交换次数。给定数组的输出只包含两种类型的元素，即 0 和 1。我们将讨论两种不同的方法来解决这个问题，其中第一种解决方案使用额外的空间来存储零的数量，而第二种解决方案只使用常量空间。

问题陈述

我们得到一个只包含两种元素 0 和 1 的数组。我们的目标是找出对给定二进制数组排序所需的最小相邻元素交换次数。

示例

Given Array: [1, 1, 0, 0, 0, 1, 0]
Result: 9 swaps required

解释

Swap 1: [0, 1, 1, 0, 0, 0, 0]
Swap 2: [0, 1, 0, 1, 0, 0, 0]
Swap 3: [0, 1, 0, 0, 1, 0, 0]
Swap 4: [0, 1, 0, 0, 0, 1, 0]
Swap 5: [0, 1, 0, 0, 0, 0, 1]
Swap 6: [0, 0, 1, 0, 0, 0, 1]
Swap 7: [0, 0, 0, 1, 0, 0, 1]
Swap 8: [0, 0, 0, 0, 1, 0, 1]
Swap 9: [0, 0, 0, 0, 0, 1, 1]

现在让我们讨论一个简单的解决这个问题的方法。

方法 1

在这种方法中，我们将计算 0 和 1 的总数，我们可以通过计算每个 1 后出现的 0 的数量然后将它们加起来来做到这一点。众所周知，排序后所有 1 将位于最右边，所有 0 将位于数组的最左边。这意味着我们必须将数组中每个 1 与其右边的每个 0 交换。数组中每个 1 所需的交换次数是数组中其右边出现的 0 的总数。我们将继续为每个 1 添加其左边出现的 0 的总数，以获得所需的交换次数。

示例

在下面的示例中，我们创建一个包含七个数字的二进制数组。我们使用上述方法找到对数组进行排序所需的最小相邻交换次数。

#include <bits/stdc++.h>
using namespace std;

// this function calculates the minimum number of swaps
int minimum_number_of_swaps(int given_array[], int nums){
   int Number_of_zeroes[nums];
   memset( Number_of_zeroes, 0, sizeof(Number_of_zeroes));
   int iterator, number = 0;
   Number_of_zeroes[nums - 1] = 1 - given_array[nums - 1];
   for (iterator = nums - 2; iterator >= 0; iterator--) {
      Number_of_zeroes[iterator] = Number_of_zeroes[iterator + 1];
      if (given_array[iterator] == 0)
      Number_of_zeroes[iterator]++;
   }
   for (iterator = 0; iterator < nums; iterator++) {
      if (given_array[iterator] == 1)
      number += Number_of_zeroes[iterator];
   }
   return number;
}
// main code goes from here
int main(){
   int given_array[] = { 1, 1, 0, 0, 0, 1, 0 };
   int nums = sizeof(given_array) / sizeof(given_array[0]);
   cout  << " Minimum number of swaps required to sort the given binary array is " << minimum_number_of_swaps(given_array, nums);
   return 0;
}

输出

运行上面的 C++ 程序后，将产生以下输出：

Minimum number of swaps required to sort the given binary array is 9

这种方法的时间复杂度 − 由于我们在一个循环中迭代 n 次，时间复杂度为：O(n)

空间复杂度 − 由于我们使用了额外的数组来存储零的数量，这种方法的空间复杂度为 O(n)

现在让我们来看一个更好、更高效的解决同一问题的方法。我们的新解决方案节省了内存，因为它不占用任何额外空间。

方法 2

在这种方法中，我们将辅助空间最小化到常量空间。我们将从最后开始迭代并计算遇到的所有零，而不是从开头读取数组。如果我们得到一个 1，则将其 1 放入排序位置所需的交换次数是我们之前遇到的零的数量。

示例

以下是上述方法的 C++ 实现：

#include <iostream>
using namespace std;

// this function finds out the least number of swaps needed
int minimum_number_of_swaps(int nums[], int number){
   int c = 0;
   int zeros_unplaced = 0;
   for(int iterator=number-1;iterator>=0;iterator--){
      if(nums[iterator] == 0)
      zeros_unplaced += 1;
      if(nums[iterator] == 1)
      c += zeros_unplaced;
   }
   return c;
}
// Main code goes here
int main(){
   int nums[] = { 1, 1, 0, 0, 0, 1, 0 };
   cout<< " Minimum number of swaps required to sort the given binary array is " << minimum_number_of_swaps(nums, 7);
   return 0;
}

输出

运行上面的 C++ 程序后，将产生以下输出：

Minimum number of swaps required to sort the given binary array is 9

这种方法的时间复杂度 − 由于我们在一个循环中迭代 n 次，时间复杂度为：O(n)

空间复杂度 − 由于我们没有使用任何额外空间，因此空间复杂度为线性，即 O(1)。

在本文中，我们讨论了两种计算对仅包含 0 和 1 的数组进行排序所需的最小交换次数的方法。在第一种方法中，我们使用了一个额外的数组来存储我们每一步的解决方案，而在第二种方法中，我们以常量空间完成了它，从而获得了更好的空间复杂度。