非递减就是升序,只不过有些元素是重复的。
根据样例,上下对比一下,可以想到先排好序,然后一个一个对比,不一样的就是需要移动的。不是求移动步数,是求需要移动的元素个数。
桶排序,遍历所有桶,直到所有桶中都没有元素。
class Solution {
public int heightChecker(int[] heights) {
int barrel[] = new int[101];
for(int height : heights){
barrel[height]++;//下标0不用
}
int count = 0;
for(int i=1,j=0;i<barrel.length;i++){
while(barrel[i]-- > 0){
if(i != heights[j++]) count++;
}
}
return count;
}
}