欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

荐 【5分钟力扣】1051. 高度检查器(python3实现)

程序员文章站 2022-06-11 17:55:23
每天五分钟,看懂一道简单、中等难度的算法题,尽可能将复杂的题讲清楚。...

一、前言

让人成长的不是岁月,而是经历。

每天五分钟,看懂一道简单、中等难度的算法题,尽可能将复杂的题讲清楚。

疯狂学习python中,2020-07-15更新

荐
                                                        【5分钟力扣】1051. 高度检查器(python3实现)

二、题目

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

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

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

示例一:

输入:heights = [1,1,4,2,1,3]
输出:3
解释:
当前数组:[1,1,4,2,1,3]
目标数组:[1,1,1,2,3,4]
在下标 2 处(从 0 开始计数)出现 4 vs 1 ,所以我们必须移动这名学生。
在下标 4 处(从 0 开始计数)出现 1 vs 3 ,所以我们必须移动这名学生。
在下标 5 处(从 0 开始计数)出现 3 vs 4 ,所以我们必须移动这名学生。

示例二:

heights = [5,1,2,3,4]
输出:5

示例三:

heights = [1,2,3,4,5]
输出:0

提示:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/height-checker/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

三、解题思路

这是一道典型的数组排序题目,问题描述有很大歧义,其实就是简单的求排序后和排序前位置不一样的个数。

如图所示:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qI1qGWMH-1594804816993)(C:\Users\Administrator\Desktop\截图\2020-07\2020-07-15-17:01:46-15.png)]
荐
                                                        【5分钟力扣】1051. 高度检查器(python3实现)

所以:

heights = [1, 1, 4, 3, 5]

输入:2

简单说,就是将排队前的数组和排队后的数组进行比较,看谁没有站在位置上。

四、代码实例:

解法一:
heights = [1, 1, 4, 3, 5]
class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        res = sorted(heights)
        count = 0
        for i in range(len(heights)):
            if res[i] != heights[i]:
                count += 1
        return count


if __name__ == '__main__':
    obj = Solution()
    print(obj.heightChecker(heights))
解法二:
heights = [1, 1, 4, 3, 5]
class Solution:
    return sum(map(lambda x: x[0]!= x[1],zip(heights,sorted(heights))))

"""
zip函数将两个列表,打包成一个个元组,然后调用map函数方法,通过匿名表达式得到一个新的 list 并返回,改list元素为True或者False
True或者False是逻辑值,在参与计算时,相等于1或者0

"""

if __name__ == '__main__':
    obj = Solution()
    print(obj.heightChecker(heights))

结果:

2

拓展知识:

map()是 Python 内置的高阶函数,它接收一个函数 f 和一个 list,并通过把函数 f 依次作用在 list 的每个元素上,得到一个新的 list 并返回。

荐
                                                        【5分钟力扣】1051. 高度检查器(python3实现)

本文地址:https://blog.csdn.net/weixin_42444693/article/details/107366165