数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
