高度检查器
难度:
标签:
题目描述
代码结果
运行时间: 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非常大或非常小,这种方法的效率如何?
▷🦆
如果输入数组已经是部分排序的状态,这种情况下算法的表现如何?会不会更高效?
▷