[Swift]LeetCode977.有序数组的平方|SquaresofaSortedArray

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

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

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

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

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

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

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

示例 2：

输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。

300ms

 1 class Solution {
 2     func sortedSquares(_ A: [Int]) -> [Int] {
 3     if A.count == 1 {
 4         return A.map{
 5             $0 * $0
 6         }
 7     }
 8     
 9     var result: [Int] = [Int]()
10     var i: Int = 0
11     var j: Int = A.count - 1
12     
13     while i != j {
14         if module(A[i]) >= module(A[j]) {
15             result.append(A[i] * A[i])
16             i += 1
17         } else {
18             result.append(A[j] * A[j])
19             j -= 1
20         }
21     }
22     result.append(A[i] * A[i])
23     
24     return result.reversed()
25 }
26 
27 func module(_ number: Int) -> Int {
28     if number < 0 {
29         return -number
30     } else {
31         return number
32     }
33  }
34 }

308ms

 1 class Solution {
 2     func sortedSquares(_ A: [Int]) -> [Int] {
 3         var ans = [Int]()
 4         
 5         if let posI = A.firstIndex(where: { $0 >= 0 }) {
 6             var left = posI - 1
 7             var right = posI
 8             
 9             while left >= 0 || right < A.count {
10                 if left >= 0 && (right >= A.count || A[left] * A[left] < A[right] * A[right]) {
11                     ans.append(A[left] * A[left])
12                     left -= 1
13                 } else {
14                     ans.append(A[right] * A[right])
15                     right += 1
16                 }
17             }
18         } else {
19             // if no value is larger than 0 -> all of them are negative
20             for i in (0..<A.count).reversed() {
21                 ans.append(A[i] * A[i])
22             }
23         }
24             
25         return ans
26     }
27 }

356ms

 1 class Solution {
 2     func sortedSquares(_ A: [Int]) -> [Int] {
 3         var maxNumber = 0
 4         var map:[Int:Int] = [:]
 5         for i in 0 ..< A.count {
 6             maxNumber = max(maxNumber, abs(A[i]))
 7             let key = abs(A[i])
 8             if let v = map[key] {
 9                 map[abs(A[i])] = v + 1
10             }else {
11                 map[abs(A[i])] = 1
12             }
13         }
14         var output:[Int] = []
15         for i in 0 ... maxNumber {
16             if let count = map[i] {
17                 let value = i*i
18                 if count == 1 {
19                     output.append(value)
20                 } else {
21                     output += Array(repeating: value, count: count)
22                 }
23             }
24         }
25         return output
26     }
27 }

376ms

1 class Solution {
2     func sortedSquares(_ A: [Int]) -> [Int] {
3         return A.map({$0 * $0}).sorted()
4     }
5 }

380ms

 1 class Solution {
 2     func sortedSquares(_ A: [Int]) -> [Int] {
 3         var nonSortedArray = [Int]()
 4         for value in A {
 5            nonSortedArray.append(value * value)
 6         }
 7         
 8         return nonSortedArray.sorted()
 9     }
10 }

400ms

1 class Solution {
2     func sortedSquares(_ A: [Int]) -> [Int] {
3          return A.reduce(into: [], { $0.append($1 * $1) }).sorted(by: <)
4     }
5 }

404ms

1 class Solution {
2     func sortedSquares(_ A: [Int]) -> [Int] {
3         return A.lazy.map{$0 * $0}.sorted(by: {$0 < $1})
4     }
5 }

416ms

1 class Solution {
2     func sortedSquares(_ A: [Int]) -> [Int] {
3         return A.map { Int(pow(Double($0), 2)) }.sorted()
4     }
5 }

6284ms

 1 class Solution {
 2     func sortedSquares(_ A: [Int]) -> [Int] {
 3         var A = A.map{ abs($0) }
 4         func fastSort(_ B: [Int]) -> [Int] {
 5             guard !B.isEmpty else { return [] }
 6             let midIndex = B.count/2
 7             return fastSort(Array(B.filter{ $0 < B[midIndex] })) + Array(B.filter{ $0 == B[midIndex] }) + fastSort(Array(B.filter{ $0 > B[midIndex] }))
 8         }
 9         return fastSort(A).map{ $0*$0 }
10     }
11 }