leetcode
leetcode 1001 ~ 1050
高度检查器

高度检查器

难度:

标签:

题目描述

代码结果

运行时间: 20 ms, 内存: 16.0 MB


/*
 * 思路:
 * 1. 使用 Java Stream API 处理数组。
 * 2. 复制 heights 数组并排序为 expected。
 * 3. 使用 Stream 计算不匹配的元素数量。
 */
import java.util.*;
import java.util.stream.IntStream;

public class Solution {
    public int heightChecker(int[] heights) {
        // 复制并排序 heights 作为 expected
        int[] expected = Arrays.stream(heights).sorted().toArray();
        // 使用 IntStream 比较两个数组的元素并计数不匹配的数量
        return (int) IntStream.range(0, heights.length)
            .filter(i -> heights[i] != expected[i])
            .count();
    }
}

解释

方法:

该题解的思路是先对输入的高度数组进行排序,得到一个非递减顺序的新数组。然后,通过比较排序前和排序后的数组的对应位置的元素,统计有多少位置的元素是不同的。这些不同的元素的数量即为需要调整的学生数量。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么选择排序然后比较两个数组的方法来解决这个问题,而不是直接在原数组上进行操作?
选择排序然后比较两个数组的方法能够直观并准确地找出哪些学生的位置需要调整以满足非递减顺序的要求。直接在原数组上操作,如尝试原地修改或调整,可能会更复杂且难以直接统计需要调整的学生数量。通过排序得到一个理想状态的数组,可以简单地通过逐对比较来确定哪些位置的学生不在正确的位置上。
🦆
在比较原数组和排序后数组的元素时,是否有可能通过一次遍历同时完成排序和比较?
通过一次遍历同时完成排序和比较是不可能的,因为排序本身是一个复杂的过程,通常需要多个步骤和多次遍历才能完成。例如,快速排序、归并排序等都涉及多次比较和交换操作,且在完成整个排序前无法得到部分的正确顺序。因此,必须先完成排序,然后再进行遍历比较。
🦆
算法中间接提到数组长度为n,如果n非常大或非常小,这种方法的效率如何?
如果n非常大,排序操作(通常为O(n log n)时间复杂度)将是主要的性能瓶颈。在极大的数据量下,排序的时间消耗可能会显著,而遍历比较的O(n)复杂度相对较小。如果n非常小,排序和比较的时间消耗都将非常低,因此算法会非常快。总的来说,这种方法在n较大时可能不是最优的,特别是当存在时间限制时。
🦆
如果输入数组已经是部分排序的状态,这种情况下算法的表现如何?会不会更高效?
如果输入数组已经部分排序,排序算法的表现依赖于具体使用的排序技术。例如,一些排序算法(如插入排序)在面对几乎已排序的数组时可以接近O(n)的效率。然而,对于大多数情况,尤其是使用诸如快速排序、归并排序这类不特别优化对于部分排序数组的算法,效率提升可能并不显著。总体上,虽然部分排序可能帮助一些,但通常不会大幅改变算法的整体性能。

相关问题