Leetcode Note: Go - How Many Numbers Are Smaller Than the Current Number
How Many Numbers Are Smaller Than the Current Number - LeetCode
https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/
- Go 言語で取り組んだメモ
回答
O(N), O(NlogN), O(n^2) 3 + α different solutions in Go - How Many Numbers Are Smaller Than the Current Number - LeetCode
https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/solutions/526266/o-n-o-nlogn-o-n-2-3-different-solutions-in-go/
func smallerNumbersThanCurrent(nums []int) []int {
occurrences := [101]int{}
for _, num := range nums {
occurrences[num]++
}
prevOccurrences := occurrences[0]
occurrences[0] = 0
for i := range occurrences[1:] {
occurrences[i+1], prevOccurrences = prevOccurrences, prevOccurrences+occurrences[i+1]
}
counts := make([]int, len(nums))
for i, num := range nums {
counts[i] = occurrences[num]
}
return counts
}