[Swift]LeetCode915.将分区数组分成不相交的间隔 | Partition Array into Disjoint Intervals

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）

➤GitHub地址：https://github.com/strengthen/LeetCode

➤原文地址：https://www.cnblogs.com/strengthen/p/9856730.html

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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

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

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

Given an array A, partition it into two (contiguous) subarrays left and right so that:

• Every element in left is less than or equal to every element in right.
• left and right are non-empty.
• left has the smallest possible size.

Return the length of left after such a partitioning. It is guaranteed that such a partitioning exists.

Example 1:

Input: [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]

Example 2:

Input: [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]

Note:

1. 2 <= A.length <= 30000
2. 0 <= A[i] <= 10^6
3. It is guaranteed there is at least one way to partition A as described.

给定的阵列A，它划分为两个（连续的）子阵列 left 和right 使得：

• 每个元素left 都小于或等于中的每个元素right。
• left并且right是非空的。
• left 具有尽可能小的尺寸。

返回长度的left这样的划分之后。保证存在这样的分区。

例1：

输入：[5,0,3,8,6] 
输出：3 
说明：左= [5,0,3]，右= [8,6]

例2：

输入：[1,1,1,0,6,12] 
输出：4 
说明：左= [1,1,1,0]，右= [6,12]

注意：

1. 2 <= A.length <= 30000
2. 0 <= A[i] <= 10^6
3. 保证至少有一种分区方式如上所述A。

36ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3 
 4         var maxSoFar = A[0], previousMax = A[0], answer = 1
 5         
 6         for i in 0..<A.count {
 7             
 8             if A[i] < maxSoFar &&
 9                 A[i] < previousMax {
10                 answer = i + 1
11                 previousMax = maxSoFar
12             } else if A[i] > maxSoFar {
13                 maxSoFar = A[i]
14             }
15         }
16         
17         return answer
18     }
19 }

56ms

 1 class Solution {
 2      func partitionDisjoint(_ A: [Int]) -> Int {
 3         if A.isEmpty {
 4             return 0
 5         }
 6 
 7         var indexAndMin: (Int, Int) = (0, A[0])
 8 
 9         // find min - O(N)
10         for (i, v) in A.enumerated() {
11             if indexAndMin.1 >= v {
12                 indexAndMin = (i, v)
13             }
14         }
15 
16         // find left max - O(N)
17         var leftMax = 0
18         for i in 0...indexAndMin.0 {
19             leftMax = max(A[i], leftMax)
20         }
21 
22         // find right less - O(N)
23         var pivotIndex = 0
24         var leftMaxCandidate = leftMax
25         var i = indexAndMin.0
26 
27         while i < A.count {
28             leftMaxCandidate = max(A[i], leftMaxCandidate)
29 
30             if A[i] < leftMax {
31                 leftMax = leftMaxCandidate
32                 pivotIndex = i
33             }
34             i += 1
35         }
36 
37         return pivotIndex + 1
38     }
39 }

60ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var dpM = [Int](repeating: 0, count: A.count)
 4         var dpm = [Int](repeating: 0, count: A.count)
 5         var M = 0
 6         var m = Int(Int32.max)
 7         for i in 0 ..< A.count {
 8             M = max(M, A[i])
 9             dpM[i] = M
10         }
11         for i in (0 ..< A.count).reversed() {
12             m = min(m, A[i])
13             dpm[i] = m
14         }
15         for i in 0 ..< A.count-1 {
16             if dpM[i] <= dpm[i+1] {
17                 return i+1
18             } 
19         }
20         return -1
21         
22     }
23 }

80ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var leftBiggest = Array(repeating: 0, count: A.count)
 4         var rightSmallest = Array(repeating: 0, count: A.count)
 5         
 6         leftBiggest[0] = A[0]
 7         for i in 1..<A.count {
 8             leftBiggest[i] = max(leftBiggest[i-1], A[i])
 9         }
10         
11         rightSmallest[A.count - 1] = A[A.count - 1]
12         for i in (0..<A.count-1).reversed() {
13             rightSmallest[i] = min(rightSmallest[i+1], A[i])
14         }
15         
16         for i in 0..<A.count-1 {
17             if leftBiggest[i] <= rightSmallest[i+1] {
18                 return i + 1
19             }
20         }
21         
22         return -1
23     }
24 }

104ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var maxArray = A
 4         var minArray = A
 5         for i in 1..<maxArray.count {
 6             maxArray[i] = max(maxArray[i], maxArray[i - 1])
 7         }
 8         for i in (0...maxArray.count - 2).reversed() {
 9             minArray[i] = min(A[i + 1], minArray[i + 1])
10         }
11         for i in 0...A.count - 1 {
12             if maxArray[i] <= minArray[i] {
13                 return i + 1
14             }
15         }
16         return -1
17     }
18 }

120ms

 1 class Solution {
 2         var debug = false
 3         init(debug: Bool = false) {
 4             self.debug = debug
 5         }
 6         func partitionDisjoint(_ A: [Int]) -> Int {
 7             return partitionDisjoint(A, start: 0, end: A.count - 1, leftMax: -1)
 8         }
 9         func partitionDisjoint(_ arr: [Int], start: Int, end: Int, leftMax: Int) -> Int {
10             if debug {
11                 let subarray = arr[start...end]
12                 print("============start: \(start), end: \(end), \(subarray)")
13             }
14             var min = Int.max
15             var minIndex = -1
16             var max = -1
17             var maxIndex = -1
18             for (index, num) in arr.enumerated() where index >= start && index <= end {
19                 if num < min {
20                     min = num
21                     minIndex = index
22                 }
23                 if num >= max {
24                     max = num
25                     maxIndex = index
26                 }
27             }
28 
29             var leftMax = -1
30             var rightMin = Int.max
31             var rightMinIndex = -1
32             var partitionIndex = minIndex
33             var newStart = start
34 
35             while leftMax < 0 || leftMax > rightMin {
36                 newStart = leftMax < 0 ? start : partitionIndex
37                 partitionIndex = rightMinIndex
38                 rightMin = Int.max
39                 rightMinIndex = -1
40                 for (index, num) in arr.enumerated() where index >= newStart && index < maxIndex {
41                     if index <= partitionIndex {
42                         if num > leftMax {
43                             leftMax = num
44                         }
45                         continue
46                     }
47                     if num < rightMin {
48                         rightMin = num
49                         rightMinIndex = index
50                     }
51                     if num < leftMax {
52                         rightMinIndex = index
53                     }
54                 }
55             }
56             return partitionIndex + 1
57         }
58     }

128ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var lmax = A.first!
 4         var rmin = A[1..<A.count].min()!
 5         for i in 0...(A.count-2) {
 6             lmax = max(lmax, A[i])
 7             if (A[i]==rmin) {  rmin = A[(i+1)..<A.count].min()! }
 8             if lmax <= rmin { return i+1 }
 9         }
10         return 0
11     }
12 }

300ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var n = A.count
 4         var pre:[Int] = [Int](repeating: 0,count: n + 1)
 5         for i in 0..<n
 6         {
 7             pre[i + 1] = max(pre[i], A[i])
 8             
 9         }
10         var suf:[Int] = [Int](repeating: 0,count: n + 1)
11         suf[n] = 999999999
12         for i in (0..<n).reversed()
13         {
14             suf[i] = min(suf[i+1], A[i])
15         }
16         for i in 1..<n
17         {
18             if pre[i] <= suf[i]
19             {
20                 return i
21             }
22         }
23         fatalError()
24     }
25 }

320ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var leftMax = A[0], maxVal = A[0], len = 1
 4         for i in 1..<A.count {
 5             if A[i] < leftMax {
 6                 // A[i] is smaller, so it must be included to the left
 7                 len = i + 1
 8                 // Update leftMax to latest maxVal
 9                 leftMax = maxVal
10             } else if A[i] > maxVal {
11                 maxVal = A[i]
12             }
13         }
14         return len
15     }
16 }

324ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var localMax = A[0]
 4         var partitionIdx = 0
 5         var maxV = localMax
 6         for i in 1..<A.count{
 7             if localMax > A[i]{
 8                 localMax = maxV
 9                 partitionIdx = i
10             } else {
11                 maxV = max(maxV, A[i])
12             }
13         }
14         
15         return partitionIdx + 1
16     }
17 }

328ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var leftMax = A[0], maxVal = A[0], len = 1
 4         for i in 1..<A.count {
 5             if A[i] < leftMax {
 6                 // A[i] is smaller, so it must be included to the left
 7                 len = i + 1
 8                 // Update leftMax to latest maxVal
 9                 leftMax = maxVal
10             } else {
11                 maxVal = max(maxVal, A[i])
12             }
13         }
14         return len
15     }
16 }

340ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var minRight = [Int](repeating: 0, count: A.count)
 4         var min = Int.max
 5         for i in stride(from:A.count - 1, through: 0, by: -1) {
 6             if A[i] < min {
 7                 min = A[i]
 8             }
 9             minRight[i] = min
10             
11             if min == 0 {
12                 break
13             }
14         }
15         
16         var max = A[0]
17         for i in 1..<A.count {
18             if max <= minRight[i] {
19                 return i
20             }
21             if A[i] > max {
22                 max = A[i]
23             }
24         }
25         return 0
26     }
27 }

344ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var minArray = A
 4         for idx in (1 ..< A.count-1).reversed() {
 5             minArray[idx] = min(minArray[idx], minArray[idx+1])
 6         }
 7         var maxValue = A[0]
 8         for idx in 0 ..< A.count {
 9             maxValue = max(maxValue, A[idx])
10             if maxValue <= minArray[idx + 1] { return idx+1 }
11         }
12         fatalError()
13     }
14 }

372ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var maxSoFar = A[0], previousMax = A[0], answer = 1
 4         
 5         for i in 0..<A.count {
 6             
 7             if A[i] < maxSoFar &&
 8                 A[i] < previousMax {
 9                 answer = i + 1
10                 previousMax = maxSoFar
11             } else if A[i] > maxSoFar {
12                 maxSoFar = A[i]
13             }
14         }
15         
16         return answer
17     }
18 }

400ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var leftMax = A[0]
 4         var sorted = A.sorted()
 5         
 6         var rightMin = sorted[0]
 7         sorted.remove(at: sorted.index(of: A[0])!)
 8         var idx = 1
 9         while idx < A.count {
10             defer { idx += 1 }
11             let a = A[idx]
12             if leftMax <= rightMin {
13                 return idx
14             }
15             
16             leftMax = max(leftMax, a)
17             if sorted.count == 0 { break }
18             let t = binarySearch(sorted, a)!
19             sorted.remove(at: t)
20             rightMin = sorted[0]
21         }
22         
23         return A.count
24     }
25     
26     func binarySearch<T: Comparable>(_ a: [T], _ key: T) -> Int? {
27         var lowerBound = 0
28         var upperBound = a.count
29         while lowerBound < upperBound {
30             let midIndex = lowerBound + (upperBound - lowerBound) / 2
31             if a[midIndex] == key {
32                 return midIndex
33             } else if a[midIndex] < key {
34                 lowerBound = midIndex + 1
35             } else {
36                 upperBound = midIndex
37             }
38         }
39         return nil
40     }
41 }

496ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var leftMax = A[0]
 4         var rightMin = Int.max
 5         var sorted = A.sorted()
 6         
 7         rightMin = sorted[0]
 8         sorted.remove(at: sorted.index(of: A[0])!)
 9         var index = 1
10         while index < A.count {
11             defer { index += 1 }
12             let a = A[index]
13             if leftMax <= rightMin {
14                 return index
15             }
16             
17             leftMax = max(leftMax, a)
18             if sorted.count == 0 { break }
19             let t = binarySearch(sorted, a)!
20             //print(index, leftMax, rightMin, t)
21             //print(sorted)
22             sorted.remove(at: t)
23             rightMin = sorted[0]
24         }
25         
26         return A.count
27     }
28     
29 func binarySearch<T: Comparable>(_ a: [T], _ key: T) -> Int? {
30     var lowerBound = 0
31     var upperBound = a.count
32     while lowerBound < upperBound {
33         let midIndex = lowerBound + (upperBound - lowerBound) / 2
34         if a[midIndex] == key {
35             return midIndex
36         } else if a[midIndex] < key {
37             lowerBound = midIndex + 1
38         } else {
39             upperBound = midIndex
40         }
41     }
42     return nil
43 }
44     
45 }

552ms

 1 class Solution {
 2     func partitionDisjoint(_ A: [Int]) -> Int {
 3         var leftMax = A[0], maxVal = A[0], len = 1
 4         for i in 1..<A.count {
 5             if A[i] < leftMax {
 6                 // A[i] is smaller, so it must be included to the left
 7                 len = i + 1
 8                 // Update leftMax to latest maxVal
 9                 leftMax = maxVal
10             } else if A[i] > maxVal{
11                 maxVal = A[i]
12             }
13         }
14         return len
15     }
16 }