1051. 高度检查器

学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。

请你返回能让所有学生以 非递减 高度排列的最小必要移动人数。

注意，当一组学生被选中时，他们之间可以以任何可能的方式重新排序，而未被选中的学生应该保持不动。

暴力理解

我理解这道题的本质就是对数组排序，然后比较排序好的数组和原数组之间各个索引处的元素是不是变了

        public static int heightChecker(int[] heights) {
            int[] arr = Arrays.copyOf(heights, heights.length);
            Arrays.sort(arr);

            int count = 0;
            for (int i = 0; i < arr.length; i++){
                if (arr[i] != heights[i]){
                    count++;
                }
            }

            return count;
        }

活用桶排序⭐⭐⭐⭐⭐

思路很巧妙

    public int heightChecker(int[] heights) {
        int[] arr = new int[101];
        for (int height : heights) {
            arr[height]++;
        }
        int count = 0;
        for (int i = 1, j = 0; i < arr.length; i++) {
            while (arr[i]-- > 0) {
                if (heights[j++] != i) count++;
            }
        }
        return count;
    }

复杂度分析:
时间复杂度：O(n)O(n) ，计数过程为 O(n)O(n)，比较过程外层循环次数固定为 100，里层循环一共也只会执行 nn 次，O(100+n)O(100+n)，即 O(n)O(n)
空间复杂度：O(1)O(1) ，其中一个固定长度的计数数组与一个统计变量，与输入 NN 的大小无关