首頁 > 後端開發 > C++ > 對一個包含兩種類型元素的陣列進行排序

對一個包含兩種類型元素的陣列進行排序

王林
發布: 2023-09-02 14:21:05
轉載
594 人瀏覽過

對一個包含兩種類型元素的陣列進行排序

有不同的方法來對只包含兩個元素(即只有1和0)的陣列進行排序。我們將討論三種不同的方法來實現這個目標。第一種方法簡單地使用預先定義的sort()函數對給定的陣列進行排序。第二種方法是計數排序方法,我們將計算0和1的數量,然後透過先寫入0的次數來更新數組,然後寫入1的次數。在最後一種方法中,我們使用了雙指標方法。

問題陳述

我們被給定一個只包含1和0的陣列。我們的任務是將所有的0和1排列,使得1在陣列的最右邊,0在陣列的左邊

Example

的中文翻譯為:

範例

1

2

Given array: a[] = [ 1, 1, 0, 1, 0, 1, 0, 1 ]

Resultant array: a[] = [ 0, 0, 0, 1, 1, 1, 1, 1 ]

登入後複製

方法一:暴力破解法。

在此方法中,我們將直接使用 sort() 函數對陣列進行排序。由於1>0,排序後,所有1都會排列在數組的右側,所有0都會排列在左側。

Sort() 函數:Sort() 函數需要 O(NlogN) 時間並以升序傳回陣列。

Example

的中文翻譯為:

範例

下面是一個C 實現,用於對包含兩種類型元素的數組進行排序。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

#include <bits/stdc++.h>

using namespace std;

int main(){

   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 };

   int len = sizeof(a) / sizeof( a[0] );

    

   // sort function to

   // sort the array

   sort( a, a + len);

   cout<< " After sorting the array, the array obtained is ";

   for(int iterator =0; iterator<len; iterator++){

      cout << a[iterator] <<" ";

   }

   return 0;

}

登入後複製

輸出

在編譯時,上述程式將產生以下輸出 -

1

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

登入後複製
登入後複製
登入後複製

方法2:計數排序方法

在這個方法中,我們將簡單地計算數組中 0 和 1 的數量,然後更新數組,其中 0 位於開頭,1 位於最後。

透過這樣做,我們將在數組的最左邊部分擁有所有的0,並在數組的最右邊部分擁有所有的1,這將自動表示所需的排序數組。

這是一種簡單的方法,但它會向數組中插入新的值,而不僅僅是交換它們的位置,因此這種方法不高效。

Example

的中文翻譯為:

範例

以下是使用 C 實作上述方法。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

#include <iostream>

using namespace std;

int main() {

   int count = 0 ;

   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 };

   int len = sizeof(a) / sizeof(a[0]);

   for(int iterator=0; iterator<len; iterator++){

      if( a[iterator] == 0 )

      count++;

   }

   for(int iterator=0 ; iterator<len ; iterator++){

      if(count){

         a[iterator] = 0 ;

         count-- ;

      }

      else a[iterator] = 1;

   }

   cout<< " After sorting the array, the array obtained is ";

   for(int iterator =0 ; iterator<len ; iterator++){

      cout<< a[iterator] << " ";

   }

   return 0;

}

登入後複製

輸出

編譯時,它將產生以下輸出 -

1

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

登入後複製
登入後複製
登入後複製

時間複雜度 - 由於我們只使用了一個循環,所以這個方法的時間複雜度為O(N)

空間複雜度 - O(1)。雖然我們使用了額外的變量,但由於它們是線性的,所以空間複雜度是常數。

方法 3:解決此問題的最佳方法

在這種方法中,我們將保留兩個指針,即start和end。我們將同時使用start指標從陣列的開頭(索引為0)開始遍歷,並使用end指標從末尾(索引為len-1)開始遍歷。

我們的任務是將所有的1排列到陣列的最右邊,這將自動將所有的0排列到陣列的左邊。

我們從初始索引開始,如果找到的元素為 1,我們將與索引「end」處的元素交換它,並將結束指標遞減 1。

如果找到的元素是0,那麼就不需要執行任何交換操作,因為它已經在最左邊的位置,我們只需將起始指標增加1即可。

Example

的中文翻譯為:

範例

以下是實作此方法的程式碼 -

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

#include <bits/stdc++.h>

using namespace std;

int main(){

   int start =0 ;

   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 } ;

   int len = sizeof(a) / sizeof( a[0] ) ;

   int end = len-1;

   while(start < end){

      if( a[start] ==1){

         swap(a[start], a[end]);

         end--;

      }

      else

         start++;

   }

   cout<< " After sorting the array, the array obtained is ";

   for(int iterator =0 ; iterator<len ; iterator++){

      cout<< a[iterator] << " ";

   }

   return 0;

}

登入後複製

輸出

1

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

登入後複製
登入後複製
登入後複製

時間複雜度 - 由於我們只遍歷數組一次,因此這種方法的時間複雜度是線性的,即 O(N)

空間複雜度 − 由於我們沒有使用任何額外的空間,所以空間複雜度為 O(1)。

結論

在本文中,我們討論了三種不同的方法來對僅包含兩種類型元素(即僅 1 和 0)的陣列進行排序。

以上是對一個包含兩種類型元素的陣列進行排序的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板