[LeetCode] 1051. Height Checker

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

Return the minimum number of students that must move in order for all students to be standing in non-decreasing order of height.

Notice that when a group of students is selected they can reorder in any possible way between themselves and the non selected students remain on their seats.

Example 1:

Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation: 
Current array : [1,1,4,2,1,3]
Target array  : [1,1,1,2,3,4]
On index 2 (0-based) we have 4 vs 1 so we have to move this student.
On index 4 (0-based) we have 1 vs 3 so we have to move this student.
On index 5 (0-based) we have 3 vs 4 so we have to move this student.

Example 2:

Input: heights = [5,1,2,3,4]
Output: 5

Example 3:

Input: heights = [1,2,3,4,5]
Output: 0

Constraints:

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

高度检查器。

学校在拍年度纪念照时，一般要求学生按照非递减的高度顺序排列。

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/height-checker
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我这里提供两种思路，一种是排序input数组，然后比较排序前后数组的区别；另一种是桶排序。

首先是排序。因为题目问的是需要移动多少个人的位置，所以当排序过后，每个人就知道他们应该站在什么位置上了。此时把排序过的和未排序过的数组进行比较，有不同的，则说明需要移动。

时间O(nlogn)

空间O(n)

Java实现

 1 class Solution {
 2     public int heightChecker(int[] heights) {
 3         int len = heights.length;
 4         int[] sorted = new int[len];
 5         for (int i = 0; i < len; i++) {
 6             sorted[i] = heights[i];
 7         }
 8         Arrays.sort(sorted);
 9 
10         int count = 0;
11         for (int i = 0; i < len; i++) {
12             if (sorted[i] != heights[i]) {
13                 count++;
14             }
15         }
16         return count;
17     }
18 }

桶排序的做法类似，但是更高效。因为身高的数据范围是[1, 100]所以我们创建101个桶，表示身高从0到100。遍历数组，统计相同身高到底有多少人。再次遍历数组，因为需要满足排列是非递减，所以我们用双指针的思路，一个指针 curHeight 指向桶排序里面的第一个桶，另一个指针 j 指向input数组。如果当前的桶 curHeight 是0，则说明没有人有当前这个身高，则curHeight++；如果当前的身高里面是有人的，则判断原数组 j 位置上的那个人的身高是否跟curHeight一样，不一样则知道这个人需要被移动。同时记得在桶排序里面要对这个curHeight的出现次数--。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int heightChecker(int[] heights) {
 3         int[] freq = new int[101];
 4         for (int h : heights) {
 5             freq[h]++;
 6         }
 7         int res = 0;
 8         int curHeight = 0;
 9         for (int i = 0; i < heights.length; i++) {
10             while (freq[curHeight] == 0) {
11                 curHeight++;
12             }
13             if (curHeight != heights[i]) {
14                 res++;
15             }
16             freq[curHeight]--;
17         }
18         return res;
19     }
20 }

LeetCode 题目总结