Leetcode Note: Go - Height Checker
Height Checker - LeetCode
https://leetcode.com/problems/height-checker/
- Go 言語で取り組んだメモ
回答
Go O(n) with explanation - no sorting involved - LeetCode Discuss
https://leetcode.com/problems/height-checker/discuss/971252/Go-O(n)-with-explanation-no-sorting-involved
const minHeight = 1
const maxHeight = 100
func heightChecker(heights []int) int {
var m [maxHeight+1]int
for _, h := range heights {
m[h]++
}
k := 0 // index of heights
count := 0
for curr := minHeight; curr <= maxHeight; curr++ {
for j := m[curr]; j > 0; j-- {
if heights[k] != curr {
count++
}
k++
}
}
return count
}