• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. 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. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap