有不同的方法可以用来最小化相邻元素之间所需的交换次数，以获得一个排序好的数组。给定的输出数组只包含两种类型的元素，即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 using namespace std;// this function calculates the minimum number of swapsint 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 输出
当你运行上面的C++程序时，它将产生以下输出 -
Minimum number of swaps required to sort the given binary array is 9
登录后复制
这种方法的时间复杂度 - 由于我们在一个循环中迭代n次，时间复杂度为：O(n)
空间复杂度 - 由于我们使用了一个额外的数组来存储零的数量，该方法的空间复杂度为O(n)
现在让我们来看一种更好、更高效的解决方案来解决同样的问题。我们的新解决方案节省了内存，因为它不占用任何额外的空间。
方法二
在这种方法中，我们将将辅助空间最小化为常量空间。而不是从开始读取数组，我们将从最后开始迭代，并计算我们遇到的所有零的数量。如果我们得到一个1，则将该1放在其排序位置所需的交换次数是在它之前遇到的零的数量。
Example
的中文翻译为：
示例
下面是上述方法的C++实现 -
#include using namespace std;// this function finds out the least number of swaps neededint 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 hereint main(){ int nums[] = { 1, 1, 0, 0, 0, 1, 0 }; cout输出
当你运行上面的C++程序时，它将产生以下输出 -
Minimum number of swaps required to sort the given binary array is 9
登录后复制
这种方法的时间复杂度 - 由于我们在一个循环中迭代n次，时间复杂度为：O(n)
空间复杂度 - 由于我们没有使用任何额外的空间，因此空间复杂度是线性的，即O(1)。
在本文中，我们讨论了两种计算排序仅包含0和1的数组所需的最小交换次数的方法。在第一种方法中，我们使用了一个额外的数组来存储每一步的解决方案，而在第二种方法中，我们在恒定的空间中完成了，从而获得了更好的空间复杂度。
以上就是给定二进制数组，需要进行的最小相邻交换次数以使其排序的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2583642.html
