1051.高度检查器（简单） - LeetCode

来源：https://leetcode-cn.com/problems/height-checker/

学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。

请你返回能让所有学生以 非递减 高度排列的最小必要移动人数。

注意，当一组学生被选中时，他们之间可以以任何可能的方式重新排序，而未被选中的学生应该保持不动。

一开始看不懂题目，后来发现直接排序比较就完事了… 时间复杂度为$O(nlogn)$O(nlogn)，空间复杂度为$O(n)$O(n)，Python实现代码：

class Solution(object):
    def heightChecker(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        temp = 0
        for a,b in zip(heights,sorted(heights)):
            if a != b:
                temp += 1
        return temp

看了题解区，发现可以用计数排序来实现速度上的提升，时间复杂度是$O(n)$O(n)，空间复杂度为$O(1)$O(1)，Python实现为：

class Solution(object):
    def heightChecker(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        arr = [0] * 101
        res = j = 0
        for val in heights:
            arr[val] += 1
        for i in range(1,101):
            while arr[i]:
                if i != heights[j]:
                    res += 1
                j += 1
                arr[i] -=1
        return res