从Leetcode 每日一题练习继续讨论：
1051. 高度检查器
1051. Height Checker
题解
本题思路上很简单, 只需将数组复制一份并排序, 再与原数组比较即可. 这里主要意图应该是让你练习一下排序算法, 因此我们手动实现一下归并排序这种比较经典的排序算法. 归并算法是经典的分治法思想, 分治法分为"分"和"治"两部分, 分即将数组一分为二, 治即对于每个子数组进行排序, 最后将排好序的两个子数组合并(归并的"并"). 对于某一类分治法, 其时间复杂度可以使用主定理进行计算(感兴趣可自行了解).
代码
func heightChecker(heights []int) int {
length := len(heights)
sorted := mergeSort(heights, length)
result := 0
for i,value := range sorted{
if value != heights[i]{
result++
}
}
return result
}
func mergeSort(input []int, length int) []int{
if length == 1{
return input
}else{
mid := length / 2
left := mergeSort(input[0:mid],mid)
right := mergeSort(input[mid:length],length-mid)
result := []int{}
j := 0
for _,value := range right{
for j<mid && left[j]<value{
result = append(result, left[j])
j++
}
result = append(result, value)
}
for j<mid{
result = append(result, left[j])
j++
}
return result
}
}