[Swift]LeetCode775.全局倒置与局部倒置|GlobalandLocalInversions

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

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

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

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

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

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

We have some permutation Aof [0, 1, ..., N - 1], where N is the length of A.

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

Return true if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.

Example 2:

Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.

Note:

A will be a permutation of [0, 1, ..., A.length - 1].
A will have length in range [1, 5000].
The time limit for this problem has been reduced.

数组 A 是 [0, 1, ..., N - 1] 的一种排列，N 是数组 A 的长度。全局倒置指的是 i,j 满足 0 <= i < j < N 并且 A[i] > A[j] ，局部倒置指的是 i 满足 0 <= i < N 并且 A[i] > A[i+1] 。

当数组 A 中全局倒置的数量等于局部倒置的数量时，返回 true 。

示例 1:

输入: A = [1,0,2]
输出: true
解释: 有 1 个全局倒置，和 1 个局部倒置。

示例 2:

输入: A = [1,2,0]
输出: false
解释: 有 2 个全局倒置，和 1 个局部倒置。

注意:

A 是 [0, 1, ..., A.length - 1] 的一种排列
A 的长度在 [1, 5000]之间
这个问题的时间限制已经减少了。

Runtime: 380 ms

Memory Usage: 19.1 MB

 1 class Solution {
 2     func isIdealPermutation(_ A: [Int]) -> Bool {
 3         for i in 0..<A.count
 4         {
 5             if abs(A[i] - i) > 1
 6             {
 7                 return false
 8             }
 9         }
10         return true
11     }
12 }

476ms

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

656ms

 1 class Solution {
 2     func merge_sort(_ array: inout[Int], _ global: inout Int, _ local: inout Int, _ start: Int, _ end: Int) {
 3         //print("[\(start), \(end))")
 4         guard end - start > 1 else { return }
 5         let mid = (start + end) / 2
 6         if mid - 1 >= start {
 7             local += array[mid - 1] > array[mid] ? 1 : 0
 8         }
 9         merge_sort(&array, &global, &local, start, mid)
10         merge_sort(&array, &global, &local, mid, end)
11         
12         let copy = Array(array[start..<mid])
13         var i = copy.startIndex, j = mid, k = start
14         while i < copy.endIndex {
15             if j >= end || copy[i] <= array[j] { 
16                 array[k] = copy[i]
17                 i += 1
18             } else {
19                 array[k] = array[j]
20                 j += 1
21                 global += copy.endIndex - i
22             }
23             k += 1
24         }
25     }
26     func isIdealPermutation(_ A: [Int]) -> Bool {
27         var global = 0, local = 0
28         var array = A
29         merge_sort(&array, &global, &local, 0, array.count)
30         return global == local
31     }
32 }

8688ms

 1 class Solution {
 2     func isIdealPermutation(_ A: [Int]) -> Bool {
 3         for i in 0..<A.count-1 {
 4             var k = i - 1
 5             if A[i] <= A[i+1] {
 6                 while k >= 0 {
 7                     if A[k] > A[i+1] { return false }
 8                     k -= 1
 9                 }
10             }
11             else {
12                 while k >= 0 {
13                     if A[k] >= A[i] { return false }
14                     if A[k] < A[i] && A[k] > A[i+1] { return false }
15                     k -= 1
16                 }
17             }
18         }
19         return true
20     }
21 }