来源：力扣（LeetCode）
描述：
排序后的高度情况用整数数组 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] 所有下标的对应学生高度都不匹配。
示例 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
方法一：基于比较的排序
思路与算法
我们可以直接将数组 heights 复制一份（记为 expected），并对数组 expected 进行排序。
待排序完成后，我们统计 heights[i] != expected[i] 的下标数量即可。
代码：
class Solution {
public:
int heightChecker(vector& heights) {
vector expected(heights);
sort(expected.begin(), expected.end());
int n = heights.size(), ans = 0;
for (int i = 0; i < n; ++i) {
if (heights[i] != expected[i]) {
++ans;
}
}
return ans;
}
};
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：8 MB, 在所有 C++ 提交中击败了13.04%的用户
复杂度分析
时间复杂度： O(nlogn)，其中 n 是数组 heights 的长度。即为排序需要的时间。
空间复杂度： O(n)，即为数组 expected 需要的空间。
方法二：计数排序
思路与算法
注意到本题中学生的高度小于等于 100，因此可以使用计数排序。
细节
在进行计数排序时，我们可以直接使用一个长度为 101 的数组，也可以先对数组 heights 进行一次遍历，找出最大值 m ，从而使用一个长度为 m+1 的数组。
当计数排序完成后，我们可以再使用一个长度为 n 的数组，显式地存储排序后的结果。为了节省空间，我们也直接在计数排序的数组上进行遍历，具体可以参考下面的代码。
代码:
class Solution {
public:
int heightChecker(vector& heights) {
int m = *max_element(heights.begin(), heights.end());
vector cnt(m + 1);
for (int h: heights) {
++cnt[h];
}
int idx = 0, ans = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= cnt[i]; ++j) {
if (heights[idx] != i) {
++ans;
}
++idx;
}
}
return ans;
}
};
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：8 MB, 在所有 C++ 提交中击败了13.04%的用户
复杂度分析
时间复杂度： O(n+C)，其中 n 是数组 heights 的长度，C 是数组 heights 中的最大值。即为计数排序需要的时间。
空间复杂度： O©，即为计数排序需要的空间。
author：LeetCode-Solution
