Height Checker
一脸懵逼的看完题, 按题意写就是o(n) space o(n) time.
1 2 3 4 5 6 7 8 9 10 11 12 |
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的速度下限的一种证明吧