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

发布时间：2020-12-14 05:06:20 所属栏目：百科来源：网络整理

导读：You are given an integer array? nums ?and you have to return a new? counts array. 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: To the ri

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: 
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.[2,1,0] 
Explanation:

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

示例:

输入: [5,1]
输出: 
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.[2,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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!