高度检查器

难度: Easy

学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。

排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。

给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。

返回满足 heights[i] != expected[i] 的 下标数量 。

示例：

输入：heights = [1,1,4,2,1,3]
输出：3 
解释：
高度：[1,1,4,2,1,3]
预期：[1,1,1,2,3,4]
下标 2 、4 、5 处的学生高度不匹配。

示例 2：

输入：heights = [5,1,2,3,4]
输出：5
解释：
高度：[5,1,2,3,4]
预期：[1,2,3,4,5]
所有下标的对应学生高度都不匹配。

示例 3：

输入：heights = [1,2,3,4,5]
输出：0
解释：
高度：[1,2,3,4,5]
预期：[1,2,3,4,5]
所有下标的对应学生高度都匹配。

提示：

1 <= heights.length <= 100
1 <= heights[i] <= 100

Submission

运行时间: 20 ms

内存: 16.0 MB

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        heights_1 = sorted(heights)
        ans = 0
        for i in range(len(heights)):
            if heights[i] != heights_1[i]:
                ans += 1
        return ans

Explain

该题解的思路是先对输入的高度数组进行排序，得到一个非递减顺序的新数组。然后，通过比较排序前和排序后的数组的对应位置的元素，统计有多少位置的元素是不同的。这些不同的元素的数量即为需要调整的学生数量。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        # 对原数组进行排序以得到预期的非递减顺序
        heights_1 = sorted(heights)
        # 初始化计数器，用来记录不匹配的位置数
        ans = 0
        # 遍历数组，比较原数组和排序后的数组的对应元素
        for i in range(len(heights)):
            if heights[i] != heights_1[i]:
                # 如果不匹配，计数器增加
                ans += 1
        # 返回不匹配的总数
        return ans

Explore

选择排序然后比较两个数组的方法能够直观并准确地找出哪些学生的位置需要调整以满足非递减顺序的要求。直接在原数组上操作，如尝试原地修改或调整，可能会更复杂且难以直接统计需要调整的学生数量。通过排序得到一个理想状态的数组，可以简单地通过逐对比较来确定哪些位置的学生不在正确的位置上。

通过一次遍历同时完成排序和比较是不可能的，因为排序本身是一个复杂的过程，通常需要多个步骤和多次遍历才能完成。例如，快速排序、归并排序等都涉及多次比较和交换操作，且在完成整个排序前无法得到部分的正确顺序。因此，必须先完成排序，然后再进行遍历比较。

如果n非常大，排序操作（通常为O(n log n)时间复杂度）将是主要的性能瓶颈。在极大的数据量下，排序的时间消耗可能会显著，而遍历比较的O(n)复杂度相对较小。如果n非常小，排序和比较的时间消耗都将非常低，因此算法会非常快。总的来说，这种方法在n较大时可能不是最优的，特别是当存在时间限制时。

如果输入数组已经部分排序，排序算法的表现依赖于具体使用的排序技术。例如，一些排序算法（如插入排序）在面对几乎已排序的数组时可以接近O(n)的效率。然而，对于大多数情况，尤其是使用诸如快速排序、归并排序这类不特别优化对于部分排序数组的算法，效率提升可能并不显著。总体上，虽然部分排序可能帮助一些，但通常不会大幅改变算法的整体性能。