給定二進制數組，需要進行的最小相鄰交換次數以使其排序

有不同的方法可以用來最小化相鄰元素之間所需的交換次數，以獲得一個排序好的陣列。給定的輸出數組只包含兩種類型的元素，即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中文網其他相關文章！