题目：高度检查器

  • 学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。
  • 请你返回至少有多少个学生没有站在正确位置数量。该人数指的是：能让所有学生以 非递减 高度排列的必要移动人数。
示例：
输入：[1,1,4,2,1,3]
输出：3
解释：
高度为 4、3 和最后一个 1 的学生，没有站在正确的位置。
提示：
  • 1 <= heights.length <= 100
  • 1 <= heights[i] <= 100

来源：力扣（LeetCode）第1051题

链接：https://leetcode-cn.com/problems/height-checker

分析：

有两种方法。都是先排序，然后比较两者之间的差异。不同处，第一种是比较排序，第二种是计数排序。计数排序的时间复杂度相对较低，本文讲解计数排序。

思路：

  • 因为heights[i]不会超过100，所以采用hash的思想，将所给数组每个值出现的次数作为值，将所给数组的值作为下标，这样相同值出现的次数就会被归在一起，而且值小的元素会在前面，因为下标就是值。
  • 如果1出现了3次，那么这3次一定是在最前面的，所以我们顺序遍历原数组，如果前3次不是1，就说明这个数要移动，以此类推。

代码：

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        ans = 0
        arr = [0] * 101  # heights[i]最多不超过100个
        for height in heights:  # 将heights散列到arr中
            arr[height] += 1
        j = 0
        for i in range(1, len(arr)):  # 根据arr中的计数排序比较原数组
            while arr[i] > 0:
                if heights[j] != i:  # 如果值不同，那么ans就+1
                    ans += 1
                j += 1
                arr[i] -= 1  # 比较完一次计数就-1，减到0说明这个数没有了。
        return ans

  • 然后再放上比较排序的代码：

    class Solution:
def heightChecker(self, heights: List[int]) -> int:
    sorted_list = sorted(heights)
    ans = 0
    for i in range(len(heights)):
        if heights[i] != sorted_list[i]:
            ans += 1
    return ans

复杂度分析：

  • 计数排序：
    • 时间复杂度：O(n) n = n + n n为数组heights的长度
    • 空间复杂度：O(1) 1 为arr的长度101
  • 比较排序：
    • 时间复杂度：O(nlogn) n 为heights的长度
    • 空间复杂度：O(n)

总结：

  • 计数排序的效率比快速排序还要快，但是只适用于特殊场景。
  • 例如在该题中，如果heights[i]的大小非常大，那么需要的内存空间会非常多。如果大小不确定，那么就无法知道该声明多长的数组，一旦内存溢出，程序就崩溃了。又比如次数非常少，基本没有重复的数，那么排序的时间也不会快到哪里去。