輸入：heights = [1,1,4,2,1,3]
輸出：3 
解釋：
高度：[1,1,4,2,1,3]
預(yù)期：[1,1,1,2,3,4]
下標(biāo) 2 、4 、5 處的學(xué)生高度不匹配。

輸入：heights = [5,1,2,3,4]
輸出：5
解釋：
高度：[5,1,2,3,4]
預(yù)期：[1,2,3,4,5]
所有下標(biāo)的對應(yīng)學(xué)生高度都不匹配。

輸入：heights = [1,2,3,4,5]
輸出：0
解釋：
高度：[1,2,3,4,5]
預(yù)期：[1,2,3,4,5]
所有下標(biāo)的對應(yīng)學(xué)生高度都匹配。

func heightChecker(heights []int) int {
    m := make(map[int]int, 100)
    for i:=0; i<len(heights); i++ {
        if _,ok := m[heights[i]]; ok {
            m[heights[i]]++
        } else {
            m[heights[i]]=1
        }
    }
    var count int
    var j int
    for i:=1; i<=100; i++ {
        if v,ok := m[i]; ok {
            for k:=1;k<=v;k++ {
                if heights[j] != i  {
                    count++
                }
                j++
            }
        }
    }
    return count 
}

class Solution(object):
    def heightChecker(self, heights):
        #桶排序 不選擇排序是因?yàn)闀r(shí)間復(fù)雜度高
        bucket = [0]*101 #身高范圍1-100
        for h in heights:
            bucket[h] += 1
        count = 0
        j = 0
        max_height = max(heights)
        for i in range(1,max_height+1):
            while bucket[i] != 0 and j < len(heights):
                if i != heights[j]:
                    count += 1
                bucket[i] -=1
                j += 1   
        return count

class Solution {
public:
    int heightChecker(vector<int>& heights) {
        int num=0;
        vector<int> p(heights);               //復(fù)制一個(gè)一模一樣的數(shù)組
        sort(heights.begin(),heights.end());  //對源數(shù)組進(jìn)行升序排序
        for(int i =0;i<heights.size();i++){   //循環(huán)比較找出位置發(fā)生變化元素的數(shù)量
            if(heights[i]!=p[i]){
                num++;
            }
        } 
        return num;
    }
};