首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 1051. 高度检查器

Leetcode 1051. 高度检查器

作者头像
zhipingChen
发布2020-01-15 16:17:00
2780
发布2020-01-15 16:17:00
举报
文章被收录于专栏:编程理解编程理解

题目描述

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

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

示例 1:

输入:1,1,4,2,1,3

输出:3

解释:

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

提示:

  1. 1 <= heights.length <= 100
  2. 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 删除

本文分享自 作者个人站点/博客 前往查看

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

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档