题目

MB{ILS8B3BHZB5G)68_E8L.png

思路

不需要进行双循环将整个数组进行排序，我们只需要有多少个数，不在它应该在的位置上，这种情况下可以使用桶排序，然后遍历出来的序列就是非递减序列。

代码

class Solution {
    public int heightChecker(int[] heights) {
        int[] arr = new int[101];  //桶排序以值的大小作为桶的大小
        for(int height:heights){
            arr[height]++;
        }
        int count = 0;
        for(int i = 0, j=0; i<arr.length;i++){
            while(arr[i]-->0){
                if(heights[j++]!=i){
                    count++;
                }
            }
        }
        return count;
    }
}