LeetCode - 1051. 高度检查器
题目描述
难度：简单
学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。
排序后的高度情况用整数数组 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]
所有下标的对应学生高度都不匹配。
提示：
1 <= heights.length <= 100
1 <= heights[i] <= 100
分析
题目很长，结合题目和示例可以分析出题目的大体意思，就是一个无序数组将它排序后，移动元素的个数；或者说是排序后数组与原数组元素一一对应之后，不一样元素的个数。
理解清楚以后，解题思路就很清晰，对数组进行排序，之后遍历数组进行对比。
代码：
public static int heightChecker(int[] heights) {
int[] ints = heights.clone();
Arrays.sort(heights);
int result = 0;
for (int i = 0; i < heights.length; i++) {
if(ints[i] != heights[i]){
++result;
}
}
return result;
}
在leetcode上跑了之后，发现效率和内存占用情况都不太好，就去翻阅了一下评论，发现了一个更有效的写法，利用桶排序来完成；
解题思路：由于题目说 1 <= heights[i] <= 100 也就是数组元素最大不超过100，那么我们可以创建长度为 101 的数组，然后将原数组中的元素作为下标，在创建数组中利用这些下标来存储每一个元素的出现次数。
int[] bucket = new int[101];
for (int height : heights) {
bucket[height]++; // 索引heigth位置的元素加一
}
之后从头遍历数组( bucket )，利用储存的值来确定原数组中的对应下标的元素是否符合要求 （ 比如桶数组中下标为 0 的桶 值为 0 ，下标为 1 的桶 值为 2，那么原数组中索引 0 和 1 的位置的值必须是 1 )。（ 结合桶排序更好理解）
代码：
public int heightChecker(int[] heights) {
int result = 0;
int[] b = new int[101];
for (int height : heights) {
b[height]++; // 索引heigth位置的元素加一
}
for(int i = 1, j = 0; i < b.length ; i++){
while (b[i]-- > 0){
if(heights[j++] != i) result++;
}
}
return result;
}
总结
第一种解法简单，理解题目意思后很好解决；第二种需要理解桶排序的概念，利用桶数组来规定原数组中元素出现的顺序与次数。
岁月悠悠，衰微只及肌肤；热忱抛却，颓废必致灵魂