使每位学生都有座位的最少移动次数
难度:
标签:
题目描述
代码结果
运行时间: 26 ms, 内存: 16.1 MB
/*
* 题目思路:
* 1. 使用Java Stream对座位和学生数组进行排序。
* 2. 然后使用Stream API计算每个学生到其最近座位的距离,
* 并将这些距离累加起来,得到总的最少移动次数。
*/
import java.util.Arrays;
public class MinMoves {
public int minMoves(int[] seats, int[] students) {
Arrays.sort(seats); // 对座位进行排序
Arrays.sort(students); // 对学生进行排序
return IntStream.range(0, seats.length) // 创建索引流
.map(i -> Math.abs(seats[i] - students[i])) // 计算每个学生到座位的距离
.sum(); // 累加得到总的最少移动次数
}
}
解释
方法:
这道题的思路是将座位和学生的位置分别进行排序,然后遍历每一个学生和座位的配对,计算他们之间的距离(即移动次数),并将所有距离累加起来。这样做的原因是,排序后的座位和学生位置可以一一对应,使得每个学生移动到最近的座位,从而最小化总的移动次数。
时间复杂度:
O(nlogn)
空间复杂度:
O(n)
代码细节讲解
🦆
在座位或学生的位置重复时,排序后的配对策略如何确保最优?例如,如果两个座位和两个学生均在同一位置,这种方法是否仍然有效?
▷🦆
对于排序后的座位和学生,为什么直接计算距离并累加是最优解?存在没有考虑的特例吗?
▷🦆
在题解的算法中,如果学生数量不等于座位数量该如何处理?
▷🦆
在实现中使用了zip函数来配对排序后的座位和学生,这种方法在座位或学生数组长度不一致时会怎样表现?
▷