Leetcode 每日一题 ------ 1051. 高度检查器

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
    }
}
2 Likes

厉害啊 佬

1 Like

刷题佬!

1 Like