Leetcode 1051. 高度检查器

zhipingChen

发布于 2020-01-15 16:17:00

3070

发布于 2020-01-15 16:17:00

文章被收录于专栏：编程理解

题目描述

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

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

示例 1:

输入：1,1,4,2,1,3

输出：3

解释：

高度为 4、3 和最后一个 1 的学生，没有站在正确的位置。

提示：

1 <= heights.length <= 100
1 <= heightsi <= 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

参考

排序算法（八）：计数排序

排序算法（九）：桶排序

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法