[Swift]LeetCode315.计算右侧小于当前元素的个数|CountofSmallerNumbersAfterSelf ...

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

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

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

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

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

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

You are given an integer array nums and you have to return a new countsarray. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

96ms

 1 class Solution {
 2     func countSmaller(_ nums: [Int]) -> [Int] {
 3         var res: [Int] = [Int](repeating: 0, count: nums.count)
 4         var vals = nums.sorted()
 5         
 6         for i in 0..<nums.count {
 7             
 8             let index = binarySearch(vals, nums[i])
 9             res[i] = index
10             vals.remove(at: index)
11         }
12         
13         return res
14     }
15     
16     func binarySearch(_ nums: [Int], _ val: Int) -> Int {
17         
18         var start = 0
19         var end = nums.count-1
20         var mid = (end - start) / 2
21         
22         while start < end {
23             
24             if nums[mid] >= val {
25                 end = mid
26             }
27             else {
28                 start = mid+1
29             }
30             mid = start + (end - start) / 2
31         }
32         
33         return mid
34     }
35 }

272ms

 1 class Solution {
 2     func countSmaller(_ nums: [Int]) -> [Int] {
 3         var res = [Int]()
 4         
 5         var sorted = nums.sorted()
 6         
 7         func inedxOf(_ v : Int, _ arr : [Int]) -> Int {
 8             var l = 0
 9             var r = arr.count-1
10             
11             while l<=r {
12                 let mid = (l+r) >> 1
13                 if arr[mid] >= v {
14                     r = mid - 1
15                 }else {
16                     l = mid + 1
17                 }
18             }
19             
20             return l
21         }
22         
23         
24         for i in 0..<nums.count {
25             let c = nums[i]
26             let index = inedxOf(c, sorted)
27             res.append(index)
28             sorted.remove(at: index)
29         }
30         
31         return res
32     }
33 }

2692ms

 1 class Solution {
 2     func countSmaller(_ nums: [Int]) -> [Int] {
 3         
 4         var counts = Array(repeating:0, count: nums.count)
 5         
 6         for i in 0..<nums.count {
 7             
 8             var nos = 0
 9             
10             for j in i+1..<nums.count {
11                 
12                 if nums[j] < nums[i] {
13                     nos += 1
14                 }                
15             }
16             
17             counts[i] = nos            
18         }
19         
20         return counts        
21     }
22 }

2924ms

 1 class Solution {
 2     func countSmaller(_ nums: [Int]) -> [Int] {
 3         var results:[Int] = []
 4         for i in 0..<nums.count {
 5             var smaller = 0
 6             for j in i..<nums.count {
 7                 if nums[j] < nums[i] {
 8                     smaller += 1
 9                 }
10             }
11             results.append(smaller)
12         }
13         return results
14     }
15 }

4168ms

 1 class Solution {
 2     func countSmaller(_ nums: [Int]) -> [Int] {
 3  var res = [Int].init()
 4     guard nums.count>0 else {
 5        return res
 6     }
 7     if nums.count == 1 {
 8         return [0]
 9     }
10     for i in 0..<nums.count-1 {
11         var count = 0
12         
13         for j in (i+1)..<nums.count{
14             if nums[j] < nums[i]{
15                 count += 1
16             }
17         }
18         res.append(count)
19     }
20     res.append(0)
21     return res
22     }
23 }