Java&C++题解与拓展——leetcode1051.高度检查器【么的新知识】

• 题目要求
• 思路一：模拟【快排】
• • Java
  • C++
  • Rust
• 思路二：模拟【计数排序】
• • Java
  • C++
  • Rust
• 总结

• 题目很简单，先根据要求排好队，其实就是递增，然后和给出的数组逐一比较计数即可。
• 排队可以用各语言内置的排序函数，通常都是基于快排的，复杂度为 O ( log ⁡ n ) O(log n) O(logn)。

class Solution {
    public int heightChecker(int[] heights) {
        int[] sortHeight = heights.clone();
        Arrays.sort(sortHeight); // 快排
        int res = 0;
        for(int i = 0; i < heights.length; i++)
            if(sortHeight[i] != heights[i])
                res++;
        return res;
    }
}

• 时间复杂度： O ( n log ⁡ n ) O(nlog n) O(nlogn)
• 空间复杂度： O ( log ⁡ n ) O(log n) O(logn)

class Solution {
public:
    int heightChecker(vector& heights) {
        vector sortHeight = heights;
        sort(sortHeight.begin(), sortHeight.end()); // 快排
        int res = 0;
        for(int i = 0; i < heights.size(); i++)
            if(sortHeight[i] != heights[i])
                res++;
        return res;
    }
};

• 时间复杂度： O ( n log ⁡ n ) O(nlog n) O(nlogn)
• 空间复杂度： O ( log ⁡ n ) O(log n) O(logn)

impl Solution {
    pub fn height_checker(heights: Vec) -> i32 {
        let mut sortHeight = heights.clone();
        sortHeight.sort(); // 快排
        sortHeight.iter().enumerate().fold(0, |acc, (i, &num)|
            if num != heights[i] { acc + 1 }
            else { acc })
    }
}

• 时间复杂度： O ( n log ⁡ n ) O(nlog n) O(nlogn)
• 空间复杂度： O ( log ⁡ n ) O(log n) O(logn)

• 用计数排序，因为数据范围小，就直接用一个数组记录每个数出现的频次依次放入排序结果。

class Solution {
    public int heightChecker(int[] heights) {
        int[] cnts = new int[110]; // 数据范围100
        for(int h : heights)
            cnts[h]++;
        int n = heights.length, res = 0;
        int[] sortHeight = new int[n];
        for(int i = 1, j = 0; i < 110; i++)
            while(cnts[i]-- > 0)
                sortHeight[j++] = i;
        for(int i = 0; i < n; i++)
            if(sortHeight[i] != heights[i])
                res++;
        return res;
    }
}

• 时间复杂度： O ( n + C ) O(n + C) O(n+C)
• 空间复杂度： O ( log ⁡ n ) O(log n) O(logn)

class Solution {
public:
    int heightChecker(vector& heights) {
        int cnts[110]; // 数据范围100
        memset(cnts, 0, sizeof(cnts));
        for(auto h : heights)
            cnts[h]++;
        int n = heights.size(), res = 0;
        int sortHeight[n];
        for(int i = 1, j = 0; i < 110; i++)
            while(cnts[i]-- > 0)
                sortHeight[j++] = i;
        for(int i = 0; i < n; i++)
            if(sortHeight[i] != heights[i])
                res++;
        return res;
    }
};

• 时间复杂度： O ( n + C ) O(n + C) O(n+C)
• 空间复杂度： O ( log ⁡ n ) O(log n) O(logn)

因为integer、i32以及一些其他类型的不熟悉，导致索引有点问题，所以暂时略过了。

简单模拟题、还契合了一下毕业季的氛围，复习一下各语言排序函数的使用方法~

假期Rust学习计划之数据类型入库。