在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ Given an array Example 1: Input: [3,2,1] Output: [3,1,2] Explanation: Swapping 2 and 1. Example 2: Input: [1,1,5] Output: [1,1,5] Explanation: This is already the smallest permutation. Example 3: Input: [1,9,4,6,7] Output: [1,7,4,6,9] Explanation: Swapping 9 and 7. Example 4: Input: [3,1,1,3] Output: [1,1,3,3] Note:
给你一个正整数的数组 如果无法这么操作,就请返回原数组。 示例 1: 输入:[3,2,1] 输出:[3,1,2] 解释: 交换 2 和 1 示例 2: 输入:[1,1,5] 输出:[1,1,5] 解释: 这已经是最小排列 示例 3: 输入:[1,9,4,6,7] 输出:[1,7,4,6,9] 解释: 交换 9 和 7 示例 4: 输入:[3,1,1,3] 输出:[1,1,3,3] 提示:
Runtime: 264 ms
Memory Usage: 21.7 MB
1 class Solution { 2 func prevPermOpt1(_ A: [Int]) -> [Int] { 3 var A = A 4 let n:Int = A.count 5 for i in stride(from:n - 1,to:0,by:-1) 6 { 7 if A[i-1] <= A[i] {continue} 8 let id:Int = i - 1 9 for j in stride(from:n - 1,to:id,by:-1) 10 { 11 if A[id] <= A[j] {continue} 12 A.swapAt(id,j) 13 return A 14 } 15 } 16 return A 17 } 18 } 268ms
1 class Solution { 2 func prevPermOpt1(_ A: [Int]) -> [Int] { 3 var A = A, i = A.count - 2 4 while i >= 0 && A[i] <= A[i+1] { 5 i -= 1 6 } 7 8 guard i >= 0 else { return A } 9 10 var lo = i + 1, hi = A.count 11 while lo < hi { 12 let mid = lo + (hi - lo) / 2 13 if A[i] > A[mid] { 14 lo = mid + 1 15 } else { 16 hi = mid 17 } 18 } 19 20 var target = lo - 1 21 while target > i && A[target] == A[target-1] { 22 target -= 1 23 } 24 A.swapAt(i, target) 25 return A 26 } 27 } 276ms 1 class Solution { 2 func prevPermOpt1(_ A: [Int]) -> [Int] { 3 var A = A, i = A.count - 2 4 while i >= 0 && A[i] <= A[i+1] { 5 i -= 1 6 } 7 8 guard i >= 0 else { return A } 9 10 var lo = i + 1, hi = A.count 11 while lo < hi { 12 let mid = lo + (hi - lo) / 2 13 if A[i] > A[mid] { 14 lo = mid + 1 15 } else { 16 hi = mid 17 } 18 } 19 20 A.swapAt(i, lo - 1) 21 return A 22 } 23 }
|
请发表评论