LeetCode-1051-高度检查器

学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。
请你返回能让所有学生以 非递减 高度排列的最小必要移动人数。
注意，当一组学生被选中时，他们之间可以以任何可能的方式重新排序，而未被选中的学生应该保持不动。

image.png

解题思路

1. 题中限制heights[i]和lenght的变化范围为1_{100，则建立容量为100的桶，key为1}100，value为出现次数；
2. 顺序遍历桶中数据，即从小到大排序的list，依次与heights中数据对比，不相同的则count++；

Python3代码：

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        # h = sorted(heights)
        # return sum(1 for i in range(len(heights)) if heights[i]!=h[i])
        # 桶排序
        t = [0 for i in range(0, 101)]
        for h in heights:
            t[h]+=1
        j = 0
        count = 0
        for i in range(1, len(t)):
            while t[i] > 0:
                t[i]-=1
                if heights[j] != i:
                    count+=1
                j += 1
        return count