Height Checker

一脸懵逼的看完题， 按题意写就是o(n) space o(n) time.

class Solution {
    public int heightChecker(int[] heights) {
        int[] t = heights.clone();
        Arrays.sort(t);
        int count = 0;
        for(int i = 0 ; i < heights.length; i++) {
            if(heights[i] != t[i])
                count++;
        }
        return count;
    }
}

想了一会儿，感觉不知道怎么优化，如果这个能优化，那么就需要知道每个元素的rank，如果rank()这个函数好像需要用一个元素比较所有元素才能知道结果，毕竟非排序数组，不比较所有元素怎么知道那个比那个大，排序也是rank的一种，这也是排序nlgn的速度下限的一种证明吧