Shulou(Shulou.com)05/31 Report--

Today, the editor will share with you the relevant knowledge points about how C++ can achieve the maximum number of sortable chunks. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

Two of the maximum number of blocks that can be sorted by Max Chunks To Make Sorted II

This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10.

Given an array arr of integers (not necessarily distinct), we split the array into some number of "chunks" (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [5, 4, 3, 2, 1]

Output: 1

Explanation:

Splitting into two or more chunks will not return the required result.

For example, splitting into [5,4], [3,2,1] will result in [4,5,1,2,3], which isn "t sorted.

Example 2:

Input: arr = [2, 1, 3, 4, 4]

Output: 4

Explanation:

We can split into two chunks, such as [2, 1], [3, 4, 4].

However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.

Note:

Arr will have length in range [1, 2000].

Arr [I] will be an integer in range [0,10 times 8].

This problem is an extension of the previous Max Chunks To Make Sorted, which says that the array is a full arrangement of all the numbers in [0, n Muth1], where n is the length of the array. On the other hand, there is no such limit on the number of this question. It can be a number greater than n, or there can be duplicate numbers. Since there is no longer much correlation between numbers and coordinates, the solution of comparing the size of numbers and coordinates in the previous question must not work. Let's look at a very clever solution. First of all, we need to make it clear that the split blocks will be sorted and put together the same as the original array. Let's use an example to illustrate:

2 1 4 3 4

1 2 3 4 4

1 2 3 4 4

We see that the first row is the original array, the second row is the sorted and spliced blocks, different colors represent different blocks, and the third row is the result of sorting the original array directly. If you look closely, you can see that the sum of the numbers that can form blocks is the same as the sum of the numbers of subarrays of the same length of the sorted array. For example, the first block is the numbers 2 and 1, and 3, while the first two digits after sorting are 1 and 2, and the sum is also 3, then we know that the first two digits of the original array can be split into one block. Similarly, the third and fourth digits in the original array are 4 and 3, and 7, respectively, and the sum of the corresponding positions of the sorted array is also 7, indicating that the block can be split. It is important to note that it is possible to exceed the maximum integer value when accumulating the sum of arrays, so we can save it with long integers. It is such a simple and violent idea that the time complexity is O (nlgn), which is mainly spent on sorting arrays. Since this problem is in the case of Max Chunks To Make Sorted's generalized, this solution can also solve the previous problem, but the time complexity is a little higher, see the code below:

Solution 1:

Class Solution {public: int maxChunksToSorted (vector& arr) {long res = 0, sum1 = 0, sum2 = 0; vector expect = arr; sort (expect.begin (), expect.end ()); for (int I = 0; I

< arr.size(); ++i) { sum1 += arr[i]; sum2 += expect[i]; if (sum1 == sum2) ++res; } return res; }}; 这道题的时间复杂度可以优化到线性，不过就是需要花点空间。下面这种解法也相当的巧妙，我们需要两个数组forward和backward，其中 foward[i] 表示 [0, i] 范围内最大的数字，而 backward[i] 表示 [i, n-1] 范围内最小的数字，实际上就是要知道已经遍历过的最大值，和还未遍历的到的最小值。为啥我们对这两个值感兴趣呢？这是本解法的精髓所在，我们知道可以拆分为块儿的前提是之后的数字不能比当前块儿中的任何数字小，不然那个较小的数字就无法排到前面。就像例子1，为啥不能拆出新块儿，就因为最小的数字在末尾。那么这里我们能拆出新块儿的条件就是，当前位置出现过的最大值小于等于之后还未遍历到的最小值时，就能拆出新块儿。比如例子2中，当 i=1 时，此时出现过的最大数字为2，未遍历到的数字中最小值为3，所以可以拆出新块儿，参见代码如下： 解法二： class Solution {public: int maxChunksToSorted(vector& arr) { int res = 1, n = arr.size(); vector f = arr, b = arr; for (int i = 1; i < n; ++i) f[i] = max(arr[i], f[i - 1]); for (int i = n - 2; i >

= 0;-- I) b [I] = min (arr [I], b [I + 1]); for (int I = 0; I < n-1; + + I) {if (f [I] = 0;-I) b [I] = min (arr [I], b [I + 1]); for (int I = 0; I < n-1; + + I) {curMax = max (curMax, arr [I]) If (curMax

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.