1051. Height Checker.md

1051. Height Checker

---

Students are asked to stand in non-decreasing order of heights for an annual photo.

Return the minimum number of students not standing in the right positions. (This is the number of students that must move in order for all students to be standing in non-decreasing order of height.)

Example 1:

Input: [1,1,4,2,1,3]
Output: 3
Explanation:
Students with heights 4, 3 and the last 1 are not standing in the right positions.

Note:

• 1 <= heights.length <= 100
• 1 <= heights[i] <= 100

---

Solution

• java

  • mine Runtime: 1 ms, faster than 88.44%, Memory Usage: 34.5 MB, less than 100.00% of Java online submissions

  //time:O(N^2)插入和选择排序 orO(Nlog2 N)快排  space:O(N)
  class Solution {
      public int heightChecker(int[] heights) {
          int[] sort = new int[heights.length];
          for(int i = 0; i < heights.length; i++){
              sort[i] = heights[i];
          }
          Arrays.sort(sort);
          int res = 0;
          int t = 0;
          for(int i = 0; i < heights.length; i++){
              if(heights[i] != sort[i]){
                  res++;
              }
          }
          return res;
      }
  }
  

  • the most votes Runtime: 0 ms, faster than 100.00%, Memory Usage: 34.5 MB, less than 100.00% of Java online submissions

  class Solution {
      public int heightChecker(int[] heights) {
          int[] heightToFreq = new int[101];
          for (int height : heights) {
              heightToFreq[height]++;
          }
          int result = 0;
          int curHeight = 0;
  
          for (int i = 0; i < heights.length; i++) {
              while (heightToFreq[curHeight] == 0) {
                  curHeight++;
              }
              if (curHeight != heights[i]) {
                  result++;
              }
              heightToFreq[curHeight]--;
          }
          return result;
      }
  }