[Swift]LeetCode768.最多能完成排序的块II|MaxChunksToMakeSortedII

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10534904.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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**8.

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**8].

这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为2000，其中的元素最大为10**8。

arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

示例 1:

输入: arr = [5,4,3,2,1]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。

示例 2:

输入: arr = [2,1,3,4,4]
输出: 4
解释:
我们可以把它分成两块，例如 [2, 1], [3, 4, 4]。
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。

注意:

arr的长度在[1, 2000]之间。
arr[i]的大小在[0, 10**8]之间。

Runtime: 56 ms

Memory Usage: 19 MB

 1 class Solution {
 2     func maxChunksToSorted(_ arr: [Int]) -> Int {
 3         var res:Int = 1
 4         var n:Int = arr.count
 5         var curMax:Int = Int.min
 6         var b:[Int] = arr
 7         for i in stride(from:n - 2,through:0,by:-1)
 8         {
 9             b[i] = min(arr[i], b[i + 1])
10         }
11         for i in 0..<(n - 1)
12         {
13             curMax = max(curMax, arr[i])
14             if curMax <= b[i + 1]
15             {
16                 res += 1            
17             }
18         }
19         return res
20     }
21 }

60ms

 1 class Solution {
 2     func maxChunksToSorted(_ arr: [Int]) -> Int {
 3         var befores: [Int] = []
 4         var afters: [Int] = []
 5         var curMax = Int.min
 6         for num in arr {
 7             if num > curMax {
 8                 curMax = num
 9             }
10             befores.append(curMax)
11         }
12         var curMin = Int.max
13         for num in arr.reversed() {
14             if num < curMin {
15                 curMin = num
16             }
17             afters.append(curMin)
18         }
19         afters.reverse()
20         var res = 0
21         for i in 0..<arr.count-1 {
22             if befores[i] <= afters[i+1] {
23                 res += 1
24             }
25         }
26         return res + 1
27     }
28 }

64ms

 1 class Solution {
 2     func maxChunksToSorted(_ arr: [Int]) -> Int {
 3         guard arr.isEmpty == false else {
 4             return 0
 5         }
 6         let sortedArr = arr.sorted()
 7         let n = arr.count
 8         var res = 0
 9         var sum1 = 0
10         var sum2 = 0
11         for i in 0..<n {
12             sum1 += arr[i]
13             sum2 += sortedArr[i]
14             if sum1 == sum2 {
15                 res += 1
16                 sum1 = 0
17                 sum2 = 0
18             }
19         }
20         return res
21     }
22 }

76ms

 1 class Solution {
 2     func maxChunksToSorted(_ arr: [Int]) -> Int {
 3         let n = arr.count
 4         var minOfRight = Array(repeating: 0, count: n)
 5         var maxOfLeft = Array(repeating: 0, count: n)
 6         
 7         maxOfLeft[0] = arr[0]
 8         minOfRight[n-1] = arr[n-1]
 9         
10         for i in 1..<n {
11             maxOfLeft[i] = max(maxOfLeft[i-1], arr[i])
12         }
13         
14         for i in (0..<(n - 1)).reversed() {
15             minOfRight[i] = min(minOfRight[i+1], arr[i])
16         }
17         
18         var res = 1
19         
20         for i in 1..<n {
21             res += maxOfLeft[i-1] <= minOfRight[i] ? 1 : 0
22         }
23         
24         return res
25     }
26 }

Runtime: 80 ms

Memory Usage: 19.3 MB

 1 class Solution {
 2     func maxChunksToSorted(_ arr: [Int]) -> Int {
 3         var nums = [Int : Int]()
 4         for item in arr {
 5             if let num = nums[item] {
 6                 nums[item] = num + 1
 7             } else {
 8                 nums[item] = 1
 9             }
10         }
11         
12         var sum = 0
13         let sortNums = nums.sorted { (dic1, dic2) -> Bool in
14             return dic1.key < dic2.key
15         }
16         for item in sortNums {
17             nums[item.key] = sum
18             sum += item.value
19         }
20         
21         let count = arr.count
22         var left = 0
23         var right = nums[arr[left]]!
24         
25         var preIndex = 0
26         var result = 0
27 
28         while left < count {
29             if arr[left] > arr[preIndex] {
30                 if let num = nums[arr[left]] {
31                     preIndex = left
32                     right = num
33                 }
34             } else if arr[left] == arr[preIndex] {
35                 left += 1
36             }
37             
38             while left <= right {
39                 if arr[left] == arr[preIndex] && left != preIndex && right < count - 1 {
40                     right += 1
41                 } else if arr[left] > arr[preIndex] {
42                     if let num = nums[arr[left]] {
43                         preIndex = left
44                         right = num
45                     }
46                 }
47                 left += 1
48             }
49             result += 1
50         }
51         return result
52     }
53 }

100ms

 1 class Solution {
 2     func maxChunksToSorted(_ arr: [Int]) -> Int {
 3         var map = [Int: Int]()
 4         var sorted = arr.sorted()
 5         var nonZeroCount = 0
 6         var result = 0
 7         for i in 0..<sorted.count {
 8             let x = arr[i]
 9             let y = sorted[i]
10             map[x] = (map[x] ?? 0) + 1
11             if map[x] == 0 {
12                 nonZeroCount -= 1
13             } else if map[x] == 1 {
14                 nonZeroCount += 1
15             }
16             map[y] = (map[y] ?? 0) - 1
17             if map[y] == 0 {
18                 nonZeroCount -= 1
19             } else if map[y] == -1 {
20                 nonZeroCount += 1
21             }
22             if nonZeroCount == 0 {
23                 result += 1
24             }
25         }
26         return result
27     }
28 }