使每位学生都有座位的最少移动次数【LC2037】
There are n seats and n students in a room. You are given an array seats of length n, where seats[i] is the position of the ith seat. You are also given the array students of length n, where students[j] is the position of the jth student.
You may perform the following move any number of times:
Increase or decrease the position of the ith student by 1 (i.e., moving the ith student from position x to x + 1 or x - 1)
Return the minimum number of moves required to move each student to a seat such that no two students are in the same seat.
Note that there may be multiple seats or students in the same position at the beginning.
元旦快乐啦
- 思路：要使总移动次数最少，那么要将每个学生移动至离其最近的座位，因此将座位和学生的位置进行升序排序，每个学生需要的移动次数即为对应位置相减，累加返回最终结果
- 实现
class Solution { public int minMovesToSeat(int[] seats, int[] students) { Arrays.sort(seats); Arrays.sort(students); int res = 0; for (int i = 0; i < seats.length; i++){ res += Math.abs(seats[i] - students[i]); } return res; } }
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
- 实现
class Solution { public int minMovesToSeat(int[] seats, int[] students) { Arrays.sort(seats); Arrays.sort(students); int res = 0; for (int i = 0; i < seats.length; i++){ res += Math.abs(seats[i] - students[i]); } return res; } }
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
