對給定二進位制陣列排序所需的最小相鄰交換次數

---

我們可以使用不同的方法來最小化對相鄰元素進行排序所需的交換次數。給定陣列的輸出只包含兩種型別的元素，即 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 的陣列進行排序所需的最小交換次數的方法。在第一種方法中，我們使用了一個額外的陣列來儲存我們每一步的解決方案，而在第二種方法中，我們以常量空間完成了它，從而獲得了更好的空間複雜度。