使每位学生都有座位的最少移动次数

难度: Easy

一个房间里有 n 个座位和 n 名学生，房间用一个数轴表示。给你一个长度为 n 的数组 seats ，其中 seats[i] 是第 i 个座位的位置。同时给你一个长度为 n 的数组 students ，其中 students[j] 是第 j 位学生的位置。

你可以执行以下操作任意次：

增加或者减少第 i 位学生的位置，每次变化量为 1 （也就是将第 i 位学生从位置 x 移动到 x + 1 或者 x - 1）

请你返回使所有学生都有座位坐的 最少移动次数 ，并确保没有两位学生的座位相同。

请注意，初始时有可能有多个座位或者多位学生在同一位置。

示例 1：

输入：seats = [3,1,5], students = [2,7,4]
输出：4
解释：学生移动方式如下：
- 第一位学生从位置 2 移动到位置 1 ，移动 1 次。
- 第二位学生从位置 7 移动到位置 5 ，移动 2 次。
- 第三位学生从位置 4 移动到位置 3 ，移动 1 次。
总共 1 + 2 + 1 = 4 次移动。

示例 2：

输入：seats = [4,1,5,9], students = [1,3,2,6]
输出：7
解释：学生移动方式如下：
- 第一位学生不移动。
- 第二位学生从位置 3 移动到位置 4 ，移动 1 次。
- 第三位学生从位置 2 移动到位置 5 ，移动 3 次。
- 第四位学生从位置 6 移动到位置 9 ，移动 3 次。
总共 0 + 1 + 3 + 3 = 7 次移动。

示例 3：

输入：seats = [2,2,6,6], students = [1,3,2,6]
输出：4
解释：学生移动方式如下：
- 第一位学生从位置 1 移动到位置 2 ，移动 1 次。
- 第二位学生从位置 3 移动到位置 6 ，移动 3 次。
- 第三位学生不移动。
- 第四位学生不移动。
总共 1 + 3 + 0 + 0 = 4 次移动。

提示：

n == seats.length == students.length
1 <= n <= 100
1 <= seats[i], students[j] <= 100

Submission

运行时间: 26 ms

内存: 16.1 MB

from typing import List

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        seats.sort()  # 对座位数组进行排序
        students.sort()  # 对学生数组进行排序
        
        moves = 0  # 记录移动次数
        
        for seat, student in zip(seats, students):
            moves += abs(seat - student)  # 计算座位和学生之间的距离并累加
        
        return moves

solution = Solution()
seats = [3, 1, 5]
students = [2, 7, 4]
print(solution.minMovesToSeat(seats, students))  # 输出: 4

seats = [4, 1, 5, 9]
students = [1, 3, 2, 6]
print(solution.minMovesToSeat(seats, students))  # 输出: 7

seats = [2, 2, 6, 6]
students = [1, 3, 2, 6]
print(solution.minMovesToSeat(seats, students))  # 输出: 4

Explain

这道题的思路是将座位和学生的位置分别进行排序，然后遍历每一个学生和座位的配对，计算他们之间的距离（即移动次数），并将所有距离累加起来。这样做的原因是，排序后的座位和学生位置可以一一对应，使得每个学生移动到最近的座位，从而最小化总的移动次数。

时间复杂度: O(nlogn)

空间复杂度: O(n)

from typing import List

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        seats.sort()  # 对座位数组进行排序
        students.sort()  # 对学生数组进行排序
        
        moves = 0  # 记录移动次数
        
        for seat, student in zip(seats, students):
            moves += abs(seat - student)  # 计算座位和学生之间的距离并累加
        
        return moves

solution = Solution()
seats = [3, 1, 5]
students = [2, 7, 4]
print(solution.minMovesToSeat(seats, students))  # 输出: 4

seats = [4, 1, 5, 9]
students = [1, 3, 2, 6]
print(solution.minMovesToSeat(seats, students))  # 输出: 7

seats = [2, 2, 6, 6]
students = [1, 3, 2, 6]
print(solution.minMovesToSeat(seats, students))  # 输出: 4

Explore

当座位或学生的位置重复时，排序后的配对策略依然有效。因为排序能确保每个座位与其最近的学生配对，即使位置重复，排序后位置相等的座位和学生仍然会对应配对。这样，即使有重复的座位或学生，每个学生仍被分配到最近的座位，从而保证了总移动次数的最小化。

直接计算排序后座位和学生的距离并累加是最优解，因为排序确保了每个学生被分配到距离最近的座位。这种方法基于贪心算法的思想：局部最优选择（即最近的座位配对）将导致全局最优解（即最小的总移动距离）。没有特殊例子能使这种策略失效，除非考虑座位或学生的特定分布情况或附加约束，但根据题目的普遍情景，此方法是适用的。

题解的基础假设是学生数量与座位数量相等。如果这两者不相等，现有的方法需要调整。例如，如果学生数量多于座位，有些学生将没有座位；如果座位多于学生，有些座位将空置。在这些情况下，需要额外的逻辑来处理多余的学生或座位，例如忽略多余的座位或额外处理无座位的学生。

Python中的zip函数在处理长度不一致的迭代器时，会停止于最短的迭代器结束。如果座位和学生数量不一致，使用zip函数将导致一些座位或学生被忽略，即只会配对数量最少的座位和学生。这可能导致一些学生没有被分配座位，或者一些座位空置，因此在学生和座位数量不匹配的情况下，需要额外的逻辑处理。