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

The knowledge points of this article "C++ method to achieve the maximum number of sortable blocks" are not quite understood by most people, so the editor summarizes the following contents for you. The content is detailed, the steps are clear, and it has a certain reference value. I hope you can get something after reading this article, let's take a look at this "C++ to achieve the largest number of sortable blocks" article.

Maximum number of blocks that can be sorted by Max Chunks To Make Sorted

Given an array arr that is a permutation of [0,1,..., arr.length-1], 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 = [4, 3, 2, 1, 0]

Output: 1

Explanation:

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

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

Example 2:

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

Output: 4

Explanation:

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

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

Note:

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

Arr [I] will be a permutation of [0,1,..., arr.length-1].

This problem gives us an array of length n, in which the numbers are all numbers in the range of [0, nMel 1], unordered. Now let's divide it into several pieces, then sort each piece separately, and then combine it together to make the original array orderly. Ask us how many blocks we can divide at most. The two examples in the topic explain the meaning of the topic very well. Let's first analyze example 1, which is an array in reverse order, and the first number is the largest, 4, so we think that the number 4 is supposed to be in the last position of the array, so it's impossible to break into a new block in the middle, otherwise the number 4 won't make it to the end. At this point of analysis, we should feel vaguely that the block where the current number is located should at least reach the place where the coordinate is the size of the current number, for example, the block where the number 4 is located should at least include the position of iTunes 4. So with this discovery, let's analyze example 2. The first number is 1, so the block where the current number 1 is located should be at least to the position of iTunes 1. Then we go to the position of iTunes 1 and find that it is the number 0, which is not beyond the range of iTunes 1, then the first two numbers can be broken into a new block. Looking back, the position of iTunes 2 is 2, which can be disconnected separately, and the following 3 and 4 can be disconnected respectively. So in fact, this problem is very similar to the Jump Game II one, we need to maintain a position that can be reached farthest, and each number here is equivalent to the jumping force in that problem, and only when we reach the farthest point, we can break the previous position into a new piece.

We iterate through the original array, using cur to represent the farthest point that can be reached, and then we traverse all the points between the current position and cur, and update cur if we encounter a larger number. When the cur is greater than or equal to the last number, we can't split the new block at this time, return the result res plus 1. Otherwise, the farthest point is reached, the variable I of the first for loop is updated, and the result res is incremented by 1. Let's look at an example:

[2 0 1 4 3]

When iTunes 0, cur=2,j=1, and then we find that the numbers of jacks 1 and 2 do not update cur, and the cur is not greater than or equal to 3, so the internal for loop is exited at this time, and the I assignment is 2, resulting in a res of 1. Then, at this point, iMagic 3, curving 4, 4, is already larger than the last 3, and directly returns res plus 1, that is, 2. See the code below:

Solution 1:

Class Solution {public: int maxChunksToSorted (vector& arr) {int res = 0, n = arr.size (); for (int I = 0; I < n; + I) {int cur = arr [I], j = I + 1; for (; j = arr.back () return res + 1;} I = j-1; + + res } return res;}}

In fact, there is a more domineering solution to this problem. If we take a closer look at some examples, we can find that the places that are broken into new blocks are all places where the previous maximum value is exactly equal to the current position coordinates. For example, in example 2, when ibasket 1, the previous maximum number is 1, so it can be disconnected. In example 1, when iTunes 4, it is equal to the maximum number 4 that has ever appeared before, and there is no point in disconnecting it now, because there are no more numbers behind it, so it is just a block. See the code below:

Solution 2:

Class Solution {public: int maxChunksToSorted (vector& arr) {int res = 0, n = arr.size (), mx = 0; for (int I = 0; I < n; + + I) {mx = max (mx, arr [I]); if (mx = = I) + res;} return res;}} The above is about "C++ to achieve the maximum number of sortable blocks" of this article, I believe we all have a certain understanding, I hope the content shared by the editor will be helpful to you, if you want to know more related knowledge, please pay attention to the industry information channel.

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.