1051. 高度检查器
排序后比较:
class Solution {
public int heightChecker(int[] heights) {
int [] temp =heights.clone();
Arrays.sort(heights);
int cnt=0;
for(int i=0;i<heights.length;i++){
if(temp[i]!=heights[i])cnt++;
}
return cnt;
}
}
计数排序
public static int heightChecker(int[] heights) {
int m = Arrays.stream(heights).max().getAsInt();
int[] cnt = new int[m + 1];
for (int h : heights) {
++cnt[h];
}
int idx = 0, ans = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= cnt[i]; ++j) {
if (heights[idx] != i) {
++ans;
}
++idx;
}
}
return ans;
}