给定二进制数组，需要进行的最小相邻交换次数以使其排序

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

问题陈述

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

Example

的中文翻译为：

示例

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

Explanation

的中文翻译为：

解释

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]

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

方法一

在这种方法中，我们将计算0和1的总数，我们可以通过计算每个1后面出现的0的数量来实现这一点，然后将它们相加。正如我们所知，所有的1都将位于数组的最右边，而所有的0都将位于数组的最左边，在排序之后。这意味着，我们必须将数组中的每个1与其右侧的每个0进行交换。数组中每个元素所需的交换次数将是数组中出现在其右侧的0的总数。我们将继续为每个1添加出现在左侧的0的总数，以获得所需的交换次数。

Example

的中文翻译为：

示例

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

#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)

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

方法二

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

Example

的中文翻译为：

示例

下面是上述方法的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的数组所需的最小交换次数的方法。在第一种方法中，我们使用了一个额外的数组来存储每一步的解决方案，而在第二种方法中，我们在恒定的空间中完成了，从而获得了更好的空间复杂度。

以上是给定二进制数组，需要进行的最小相邻交换次数以使其排序的详细内容。更多信息请关注PHP中文网其他相关文章！