LeetCode每日一题 - 高度检查器_学校打算为全体学生拍照,学生需要按照非递减的高度顺序排成一行-CSDN博客

本文链接：https://blog.csdn.net/qq_43555150/article/details/119776486

这篇博客介绍了一个C语言和Python3实现的算法，用于计算数组中学生按照非递减高度排序后与原始高度不匹配的元素数量。算法首先对原始高度数组进行排序，然后比较排序后的预期高度与原始高度的差异，返回不匹配的下标数量。在C语言的实现中，使用了冒泡排序，而在Python3中，利用内置的排序函数，实现了更快的执行速度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目：
学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照非递减的高度顺序排成一行。
排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。
给你一个整数数组 heights ，表示当前学生站位的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。
返回满足 heights[i] != expected[i] 的下标数量。

示例 1：
输入：heights = [1,1,4,2,1,3]
输出：3
解释：
高度：[1,1,4,2,1,3]
预期：[1,1,1,2,3,4]
下标 2 、4 、5 处的学生高度不匹配。
示例 2：
输入：heights = [5,1,2,3,4]
输出：5
解释：
高度：[5,1,2,3,4]
预期：[1,2,3,4,5]
所有下标的对应学生高度都不匹配。

思路：排序后数组为exp，比较exp每一位和heights不同的个数。

C语言

int heightChecker(int* heights, int heightsSize)
{
    int* exp = (int*)malloc(heightsSize * sizeof(int));
    int i, m=0, n=0,res=0;
    while(m<heightsSize)
        exp[m++] = heights[n++];
    for(i=0;i<heightsSize-1;i++)
        for(int j=i+1;j<heightsSize;j++)
            if(exp[j]<exp[i])
            {
                int tmp=exp[i];
                exp[i] = exp[j];
                exp[j] = tmp;
            }
    for(i=0;i<heightsSize;i++)
        if(exp[i] != heights[i])
            res++;
    return res;
}

执行用时4ms，内存消耗5.7MB。

Python3

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        exp = sorted(heights)
        return sum(exp[i] != heights[i] for i in range(len(heights)))