1051. 高度检查器

题目

学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。

排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。

给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。

返回满足 heights[i] != expected[i] 的 下标数量 。

示例：

输入：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]
所有下标的对应学生高度都不匹配。

示例 3：

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

提示：

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

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

思路

直接排序然后比较的方法没啥好讲的，这里因为数据在100之内，可以使用计数排序。对线性排序只是知道思想，平时写的很少，借本题复习一下。

首先开辟一个大小为101（或者为数组最大值加1）的数组freq，统计数组元素的出现频次，然后将freq从左往右依次累加，即变为自身的前缀和数组，此时，freq[i]表示小于等于i的元素个数，通过该数组就可以知道元素i在排序后应该在什么范围之内，元素i应该在[freq[i-1],freq[i])之间，注意是左闭右开。最好的理解方式是举一个例子：

输入heights=[1,1,4,2,1,3]，通过统计频次以及累加前缀得到freq=[0,3,4,5,6]，对于元素2，可以发现，不大于2的元素有freq[2]=4个，其中有freq[2-1]=3个是不大于1的，因此有freq[2]-freq[1]=1个等于2。所以对于元素来说，其排序好的下标范围是[3,4)。

最后遍历一次原数组，判断当前位置是否和其排序后的下标范围一致，不一致的话，ans++。

代码

class Solution {
    public int heightChecker(int[] heights) {
        int[] freq = new int[101];
        // 统计频次
        for (int h : heights) {
            freq[h]++;
        }
        // 累加
        for (int i = 1; i < 101; i++) {
            freq[i] += freq[i - 1];
        }
        int ans = 0;
        for (int i = 0; i < heights.length; i++) {
            // 左闭右开
            if (!(i < freq[heights[i]] && i >= freq[heights[i] - 1])) {
                ans++;
            }
        }
        return ans;
    }
}