【LeetCode】高度检查器 Java 题解

2022 年 6 月 13 日
本文字数：1167 字
阅读完需：约 4 分钟

题目描述

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

排序后的高度情况用整数数组 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]所有下标的对应学生高度都匹配。
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/height-checker著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是数组处理题目，题目容易理解，排序后的高度情况用整数数组 expected 表示，需要找出 heights[i] != expected[i] 的下标数量。
理解题目之后，我们需要做的就是对整个数组进行排序。排序问题，可以采用比较排序的方法，算法的时间复杂度是 O(n log n)。针对这个题目，我们也可以采用非比较类的计数排序。什么是计数排序呢？
计数排序是一个非基于比较的排序算法，该算法于 1954 年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中 k 是整数的范围），快于任何比较排序算法。
也就是说，我们利用数组下标是有序递增的特性，统一每一个数字出现的次数，然后输出的排序方法。记数排序利用额外的空间，提升了排序的效率。实现代码如下，供参考。

通过代码

class Solution {    public int heightChecker(int[] heights) {        int maxHeight = heights[0];        int n = heights.length;        for (int i = 1; i < n; i++) {            maxHeight = Math.max(maxHeight, heights[i]);        }        int[] cnt = new int[maxHeight + 1];        for (int height : heights) {            cnt[height]++;        }                int ans = 0;        int idx = 0;        for (int j = 0; j < maxHeight + 1; j++) {            while (cnt[j] > 0) {                if (heights[idx] != j) {                    ans++;                }                idx++;                cnt[j]--;            }        }        return ans;    }}