Leetcode 1051. 高度检查器

题目描述

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

请你返回至少有多少个学生没有站在正确位置数量。该人数指的是：能让所有学生以 非递减 高度排列的必要移动人数。

示例 1:

输入：[1,1,4,2,1,3]
输出：3
解释：
高度为 4、3 和最后一个 1 的学生，没有站在正确的位置。

提示：

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

解法

由题可知，只需要获得正确的非递减序列，然后与当前序列比较即可获得需要移动的个数。

sort排序比较

对序列进行排序，获得非递减序列，逐个元素比较。

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

计数排序比较

根据提示可知元素值范围不大，不妨申请一定值域范围的序列 arr，存储对应元素值出现的个数，此时遍历 arr 即可获得非递减序列，仍然与原序列进行逐个元素对比，获取移动个数。

此处元素值范围不大，可以每个桶只存储一个元素值对应的内容，当值空间较大时，可以针对每个桶映射一定元素值范围的内容，在桶内可以自由搭配其他的排序算法。

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        arr=[0]*101
        for e in heights:
            arr[e]+=1
        index,ret=0,0
        for i in range(1,101):
            while arr[i]>0:
                if i!=heights[index]:
                    ret+=1
                arr[i]-=1
                index+=1
        return ret

参考
排序算法（八）：计数排序
排序算法（九）：桶排序