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

概述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: Inpu

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] = index10             vals.remove(at: index)11         }12         13         return res14     }15     16     func binarySearch(_ nums: [Int],_ val: Int) -> Int {17         18         var start = 019         var end = nums.count-120         var mID = (end - start) / 221         22         while start < end {23             24             if nums[mID] >= val {25                 end = mID26             }27             else {28                 start = mID+129             }30             mID = start + (end - start) / 231         }32         33         return mID34     }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-110             11             while l<=r {12                 let mID = (l+r) >> 113                 if arr[mID] >= v {14                     r = mID - 115                 }else {16                     l = mID + 117                 }18             }19             20             return l21         }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 res32     }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 += 114                 }                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 results14     }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 = 012         13         for j in (i+1)..<nums.count{14             if nums[j] < nums[i]{15                 count += 116             }17         }18         res.append(count)19     }20     res.append(0)21     return res22     }23 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode315. 计算右侧小于当前元素的个数 | Count of Smaller Numbers After Self全部内容，希望文章能够帮你解决[Swift]LeetCode315. 计算右侧小于当前元素的个数 | Count of Smaller Numbers After Self所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。