LeetCode——1051.高度检查器

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

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

思路

咋开始看这道题，很乱，不知道乱七八糟说啥玩意儿。看来读题也是很重要的，最后仔细一想，就是为了计算当前有多少个位置的数值跟排序后的数值不一致。那就可以解决了

代码

import java.util.Arrays;

class Solution {
    public int heightChecker(int[] heights) {
        int length=heights.length;
        int test[]=new int[length];
        for (int i=0;i<length;++i)
            test[i]=heights[i];
        Arrays.sort(test);

        int count=0;//计算需要移动的人数
        for (int i=0;i<length;++i)
            if (heights[i]!=test[i])
                ++count;
        return count;
    }
}

结果

现在对于力扣的结果越来越感到不可思议了，我想这个原因，很大程度上是因为力扣的测试数据不够多，造成了两种方法本身效率提升很多但是看起来几乎没有差别。

这种解法的时间，主要花在两个循环就是O(n)和排序O（logn）的时间上。

题解改进思路

既然力扣的测试数据如此之小，我们还可以利用一个桶排序来解决排序的问题。

改机代码

class Solution {
    public int heightChecker(int[] heights) {
        int length=heights.length;
        int test[]=new int [101];//因为数值的范围是1-100，所以需要开101个位置的数组

        //把数组中的值放到桶中，这样从桶中取出来的数值就是有序的了
        for (int i=0;i<length;++i)
            test[heights[i]]++;

        int count=0;//计算不同的个数

        //遍历一遍桶
        for (int i=1,j=0;i<101;++i)
        {
            while(test[i]-->0)//从桶中每次取出一个元素，先取出来，再减去，能够保证把所有的数值都取完
                if (heights[j++]!=i)//开始遍历 heights数组，只要这个数组的对应位置，不等于从桶中取出来的数
                    ++count;        //通中取出来的数就是 i 
        }
        return  count;

    }
}

结果

题解这种解法真的妙，虽然能大概想到利用桶排序来解，不过还是这个解法很猛！学到了！