数组的最大子组，以便可以对其进行独立排序

Question

对于数组，我需要找到可以创建的最大子组数，以便 - 当所有子组单独排序然后依次放置时，整个数组都会被排序。

例如： 阵列[1, 5, 4, 9, 8, 7, 12, 13, 14]

可以形成的最大组数为6

[1], [5, 4], [9, 8, 7], [12], [13], [14]

如果我们要独立地对内部元素进行排序，然后将这些组放在一起，我们将得到一个排序的数组。

另一个例子是[4, 3, 2, 6, 1]可以形成的最大组只有1(数组本身)

请注意，数组的所有元素都是不同的。我写的程序是用以下伪代码编写的——

1. Save all elements of array A into hashmap with the element value A[i] as key 
and index i as value
2. Sort array A.
3. Initialize groupCount = 0, startIndex = -1;
3. For every element, check from hashmap if its original index is 
greater than **startIndex**. If it is greater, increment groupCount 
and set startIndex = original index of element i.
4. Finally return groupCount;

此逻辑在许多测试用例上都不起作用。你能帮我弄清楚什么是最佳逻辑吗？

Answer 1

请注意，只要当前组包含的元素集与排序数组中相应位置上出现的元素集相同，就可以结束当前组。

上述想法可以直接在O(N^2) 中实现，但在下面的观察中转换它是有用的，更容易有效地实现(可能需要花点时间才能意识到为什么上面的陈述暗示了下一个)：

• 最大组数等于索引 k 的数量，使得序列中的前 k个元素恰好是最小的k个元素。

这更容易实现，因为为了检查最小的 k + 1 项是否恰好是原始数组中的前 k + 1项，我们只能查看最小的k+ 1 项中最大的原始索引。如果这个最大的索引是k，那么我们必然有一组索引0,1，...k出现在这些第一个位置上。

下面的伪代码详细介绍了此方法。时间复杂度为O(N log(N))，由排序步骤决定。

1. Save all elements of array A into a hashmap with the element value A[i] as key 
and index i as value
2. Sort array A.
3. Initialize groupCount = 0, maxIndex = -1;
4. For k = 0 to N,
check from hashmap the original index i, of A[k]
maxIndex = max(i, maxIndex)
if maxIndex == k then increment groupCount
5. Finally return groupCount;

Answer 2

你的方法几乎是正确的。只要原始索引大于起始索引，就会递增组计数。这在许多情况下会失败，例如：5 6 3 4.

代码的工作

• 在上面的数组(即5 6 3 4)中，它将检查 5 的原始索引，该索引应为 2(按排序顺序)，并将组 Count 增加到 1，同时将起始索引设置为2
• 当它将检查原始索引 6 时，它应该是3(按排序顺序)，它将递增组 Count(2)，因为它的索引大于起始索引(即2)。这是不正确的，因为答案是1!.

改进

当您遇到 6 时，您应该在不更改组 Count 的情况下将起始索引从 2 更改为 3，并且仅当起始索引 = 原始索引时才应增加组计数。

这是我的O(NlogN)复杂性代码：

#include <bits/stdc++.h>
using namespace std;
int maxSubGroups(vector<int>arr){
int n=arr.size();
vector<int>sortedArr = arr;
sort(sortedArr.begin(), sortedArr.end());
map<int,int>m;
for(int i=0;i<sortedArr.size();i++)
m[sortedArr[i]]=i;
int maxGroups = 0, maxIndex=0;
for(int i=0;i<n;i++){
maxIndex = max(maxIndex, m[arr[i]]);
if(maxIndex == i)
maxGroups++;
}
return maxGroups;
}
int main() {
vector<int>arr = {1, 5, 4, 9, 8, 7, 12, 13, 14};
int maxGroups = maxSubGroups(arr);
cout<<maxGroups; // 6
return 0;
}

实时代码