LC1051.高度检查器

原题链接：https://leetcode.cn/problems/height-checker/
LC1051.高度检查器 - 图1

思路：计数排序

  • 相当于计算当前数组和排序之后的数组当中有多少项是不一致的
  • LC1051.高度检查器 - 图2#card=math&code=O%28n%5Clg%20n%29&id=Iaw5E)复杂度的实现是不难的，直接排序即可
  • 利用计数排序的思路可以实现稳定LC1051.高度检查器 - 图3#card=math&code=O%28n%29&id=E5Aur)时间复杂度的排序

  • 对于排序之后的结果并不关心，只关心当前位置的值是不是应该出现的最小值，如果是，那么就不变化，否则就变化

    代码

    1. class Solution {
    2. public:
    3.   int heightChecker(vector<int>& heights) {
    5.       // 记录min_num是防止出现负数
    6.       int min_num = *min_element(heights.begin(), heights.end());
    7.       int max_num = *max_element(heights.begin(), heights.end()) - min_num;
    8.       int n = heights.size();
    10.       vector<int> cnt(max_num + 5, 0);
    11.       for (int i = 0; i < n; i++) {
    12.           heights[i] -= min_num;
    13.           cnt[heights[i]] += 1;
    14.       }
    16.       int index = 0, ans = 0;
    17.       // 对于每一个数i而言，如果它在heights中出现过
    18.       // 那么就要用heights[index]和其对比，判断是否需要调整
    19.       for (int i = 0; i <= max_num; i++) {
    20.           for (int k = 0; k < cnt[i]; k++) {
    21.               if (heights[index] != i) {
    22.                   ans += 1;
    23.               }
    24.               index += 1;
    25.           }
    26.       }
    28.       return ans;
    29.   }
    30. };