1051. Height Checker

问题:

给定一组学生身高,要对其进行身高排序,从低到高。

求最少要移动几个学生的位置。

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

  

解法:

基本解法:

将身高数组排序,得到最终排序结果,和原数组比较,同一位置i上有不一样的元素,res++

 

代码参考:

 1 class Solution {
 2 public:
 3     int heightChecker(vector<int>& heights) {
 4         int res=0;
 5         vector<int>heightsOrd(heights);
 6         sort(heightsOrd.begin(), heightsOrd.end());
 7         for(int i=0; i<heights.size(); i++){
 8             if(heights[i]!=heightsOrd[i]) res++;
 9         }
10         return res;
11     }
12 };

 

不排序解法:

由于本问题的限制:身高在1~100,因此,我们可以使用桶排序的思想

设定高度计数数数组 htcnt[101]

然后再对比同一偏移,

htcnt的偏移:curh++ ,htcnt[curh]--

原高度数组偏移:h : heights

是否高度一样,不一样res++

 

代码参考:

 1 class Solution {
 2 public:
 3     int heightChecker(vector<int>& heights) {
 4         int htcnt[101]={0};
 5         for(int h:heights){
 6             htcnt[h]++;
 7         }
 8         int curh=0;
 9         int res=0;
10         for(int h:heights){
11             while(htcnt[curh]==0){
12                 curh++;
13             }
14             if(h!=curh){
15                 res++;
16             }
17             htcnt[curh]--;
18         }
19         return res;
20     }
21 };

 

上一篇:ADR(Automatic Diagnositc Repository)


下一篇:Leetcode 1414. 和为 K 的最少斐波那契数字数目(贪心)