資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中可單獨排序以構成排序陣列的最大分割槽數
給定一個包含 N 個數字的陣列，元素範圍在 0 到 N-1 之間。元素是無序的。目標是找到陣列的最大分割槽數，這些分割槽可以單獨排序，然後連線起來構成長度為 N 的完整排序陣列。
每個分割槽都選擇使得其中的元素是無序的。對於範圍在 0 到 N-1 之間的 N 個數字，排序後的元素位於與其值相等的索引處。Arr[i] = i。
我們將透過將其與左側迄今為止找到的最大值進行比較來解決此問題。當到達最大值的正確位置時，(maximum == i )。它左邊的所有元素都較小，因此可以構成一個單獨的分割槽。它右邊的所有元素都較大。現在對其餘的右側元素執行相同的過程並將其劃分為分割槽。
讓我們透過示例來理解。
輸入 − Arr[]={ 0,3,2,1,4,5 }
輸出 − 最大分割槽數 − 3
說明 − 從 0 開始，令 max=0 Arr[0]
在索引 0 和 3 之間。3 是最大值。當到達索引 i=3 ( maxx==i) 時。因此第一個分割槽是 [0,3,2,1]
對於索引 4，最大值是 4。索引 i=4 ( maxx==i)。因此第二個分割槽是 [4]
對於索引 5，最大值是 5。索引 i=5 ( maxx==i)。因此第二個分割槽是 [5]
總共 3 個分割槽 [0,3,2,1][4][5]。對每個分割槽進行排序並連線。
輸入 − Arr[]={ 5,4,3,2,1,0 }
輸出 − 最大分割槽數 − 1
說明 − 從 0 開始，令 max=0 Arr[0]
在索引 0 和 5 之間。5 是最大值。當到達索引 i=5 ( maxx==i) 時。因此只有一個分割槽 [5,4,3,2,1,0]
下面程式中使用的方法如下
我們使用一個整數陣列 Num[]，用範圍從 0 到 N 的數字初始化。
函式 partitions(int arr[], int n ) 以陣列及其長度作為引數，並返回可以單獨排序以構成整個陣列排序的最大分割槽的數量。
初始分割槽計數為 0。初始最大值為 maxx 中的 arr[0]。
對於所有從最左側元素開始的元素。查詢它是否大於 maxx。
如果 arr[i]>maxx 為真。更新 maxx。
如果當前 maxx 和索引相同。( maxx==i ) 則直到 i 的所有元素都是一個分割槽的一部分。遞增計數。
對右側的其餘元素執行此操作，直到結束。
將結果作為計數返回。
示例
#include <bits/stdc++.h>
using namespace std;
int partitions(int arr[], int n){
int count = 0;
int maxx = arr[0];
for (int i = 0; i < n; ++i) {
if(arr[i] > maxx)
maxx=arr[i];
if (maxx == i)
count++;
}
return count;
}
int main(){
int Num[] = { 2,1,0,4,5,3 };
int len = 6;
cout <<"Maximum partitions that can be sorted: "<<partitions(Num, len);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Maximum partitions that can be sorted: 18
577 次瀏覽
