学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。
请你返回至少有多少个学生没有站在正确位置数量。该人数指的是：能让所有学生以 非递减 高度排列的必要移动人数。
示例：
输入：[1,1,4,2,1,3]
输出：3
解释：
高度为 4、3 和最后一个 1 的学生，没有站在正确的位置。
提示：
1 <= heights.length <= 100
1 <= heights[i] <= 100
代码实现
C++
第一种方法：
显而易见的做法是先对数组heights按照值大小进行排序生成一个新的数组arr1，然后拿arr1和heights逐项比较。
如果heights中某一项和arr1相同位置的值不等，就说明，heights中这个同学的升高不在正确位置上，要重排。
这样统计所有不同的项，返回个数即可。
第二种方法：
我们发现，题目对数组的值和数组的长度都进行的限制，大小都在区间[1,100]。
我们可以创建一个长度为101的数组arr2，记录heights中不同的升高出现的次数。
实际上这就是排序，如下图，arr2可以认为等价于arr1：
由于这种等价关系，后面的操作和方法一中的思想是一样的，只不过，对于arr2来说，遍历意味这两种情况：
找到大于0的元素；
找到一个大于0的元素后，通过不断的循环递减次数实现类似遍历arr1的效果；
在这过程中再做比较来统计res的值。
public:int heightChecker(vector<int>& heights) {//1. 对数组进行排序vector<int> arr;//arr.swap(heights);for(int i=0; i<heights.size(); i++){arr.push_back(heights[i]);}sort(arr.begin(), arr.end());int result=0;for(int i=0; i<heights.size(); i++){//arr[i] == heights[i] 站位正确result += arr[i] == heights[i]? 0:1;}return result;}
};
class Solution {
public:int heightChecker(vector<int>& heights) {int result=0;int count[101];int index=0;memset(count, 0, sizeof(int)*101);for(int i=0; i<heights.size(); i++){count[heights[i]]++;}//以此从0到101个高度都扫描一遍，判断heigths每个位置是否依次大小排列for(int i=0; i<101; i++){for(; count[i]>0; count[i]--){if(heights[index++] != i){result++;}}}return result;}
};
Python:
class Solution(object):def heightChecker(self, heights):""":type heights: List[int]:rtype: int"""newArr = sorted(heights)return sum([x1 != x2 for x1, x2 in zip(heights, newArr)])