【刷题日记】1051. 高度检查器

本次刷题日记的第 64 篇，力扣题为：1051. 高度检查器，简单

一、题目描述：

高度检查器，是如何来检查高度的呢？了解一下

二、这道题考察了什么思想？你的思路是什么？

仔细看看题目都给我们说了啥，来翟取一下关键信息：

虽然说光看题目的文字好像不是特别明白题目具体是要我们干些啥，不过还好题目给出了 3 个示例，能够让我知道题目是想要我们实现啥

• 题目给出了一个数组，数组中的元素是整型数字，数字的排列是无序的
• 题目要求我们按照非递减的方式来将数组进行排序，且和原来的数组进行比较，将对应位置，不同身高的情况累计下来，看看总共有多少个

分析

这里我们可以知道题目至少是需要我们对原有数组进行排序的，这里需要明确的一点是题目要求我们用非递增的方式来进行排序

一开始看题目，可能会认为是，将数组中不满足非递增的元素记录下来，作为返回的结果

例如

这样来看，一开始是否还会认为，上述的数组是 元素 5 不满足非递增的要求，因此得到的结果是 1

其实并不是，题目给出了 咱们 3 个案例，实际上也是想让我们更加清晰的知道这个题需要我们干点啥

实际上我们需要这么做

实际上应该是比较上述数组对应位置元素不同的情况个数，因此一看，我们就知道不同的个数为 5 个

那么接下来咱们需要去做这个题就很明确了：

• 第一将题目给出的数组进行排序，这里我们可以使用自己来实现排序算法，也可以使用 golang 中提供的库函数来进行处理，毕竟实际工作中，自己写的排序算法也很难排上用场，库函数肯定比绝大多数人实现的算法要更优
• 第二我们需要用排序后的数组，与原有的数组进行挨个比较，记录元素不同的个数

虽然本题很简单，重要的是我们得有一个做题的明确思路和感觉

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

编码如下：

func heightChecker(heights []int) int {
    // 开辟空间，不能直接修改原有空间，因为后续我们需要用来比较
    help  := append([]int{}, heights...)
    // 使用库函数进行排序
    sort.Ints(help)
    res := 0
    // 比较并记录结果
    for i, v := range heights {
        if v != help[i] {
            res++
        }
    }
    return res
}

四、总结：

这种实现方式空间复杂度非常明确，因为咱们开辟了一个 help 数组，假设算作占用 n 的空间，因此空间复杂度是 O(n)

时间复杂度，咱们使用库函数的话，库函数的具体实现方式时间复杂度是 O(nlogn)

原题地址：1051. 高度检查器

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~