leetcode 2037. Minimum Number of Moves to Seat Everyone(python)
描述
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.
Example 1:
Input: seats = [3,1,5], students = [2,7,4] Output: 4 Explanation: The students are moved as follows: - The first student is moved from from position 2 to position 1 using 1 move. - The second student is moved from from position 7 to position 5 using 2 moves. - The third student is moved from from position 4 to position 3 using 1 move. In total, 1 + 2 + 1 = 4 moves were used. 复制代码
Example 2:
Input: seats = [4,1,5,9], students = [1,3,2,6] Output: 7 Explanation: The students are moved as follows: - The first student is not moved. - The second student is moved from from position 3 to position 4 using 1 move. - The third student is moved from from position 2 to position 5 using 3 moves. - The fourth student is moved from from position 6 to position 9 using 3 moves. In total, 0 + 1 + 3 + 3 = 7 moves were used.复制代码
Example 3:
Input: seats = [2,2,6,6], students = [1,3,2,6] Output: 4 Explanation: The students are moved as follows: - The first student is moved from from position 1 to position 2 using 1 move. - The second student is moved from from position 3 to position 6 using 3 moves. - The third student is not moved. - The fourth student is not moved. In total, 1 + 3 + 0 + 0 = 4 moves were used.复制代码
Note:
n == seats.length == students.length 1 <= n <= 100 1 <= seats[i], students[j] <= 100复制代码
解析
根据题意,给出了有 n 个座位的列表 seats ,其中 seats[i] 表示的是座位号,同时又给出了有 n 个学生的列表 students ,其中 students[i] 表示的是该学生现在做的座位号,我们可以执行以下的操作无数次:
将一个学生移动到其座位号增加一个的位置或者减少一个的位置,比如将座位号为 3 的学生可以移动到座位号为 2 或者 4 的位置上
题目要求我们执行多少次上述操作,可以将 students 中的学生都安排到 seats 座位上,且没有两个学生坐在同一个座位上。其实思路很简单,就是个找规律题。
假如 seats = [12,14,19,19,12] ,students = [19,2,17,20,7] ,我们先经过排序可以得到:
seats = [12,12,14,19,19] students = [2,7,17,19,20]复制代码
我们可以发现 students[0] 学生离得最近的座位号就是 seats[0] ,seats[1] 及其后面的座位肯定相等或者更远不做考虑,此时 seats[0] 就被占了
students[1] 学生离得最近的座位号就是 seats[0] 和 seats[1],
seats[2] 及其后面的座位肯定相等或者更远不做考虑,但是 seats[0] 已经被占,所以离得最近的座位就是 seats[1]
students[2] 学生离得最近的座位号就是 seats[1] 和 seats[2],
seats[3] 及其后面的座位肯定相等或者更远不做考虑,但是 seats[1] 已经被占,所以离得最近的座位就是 seats[2]
同样的规律继续进行下去我们发现,其实相同索引 i 的 seats[i] 的座位就是 students[i] 离的最近的位置,直接将 abs(seats[i]-students[i]) 加入结果中即可得到结果。
解答
class Solution(object): def minMovesToSeat(self, seats, students): """ :type seats: List[int] :type students: List[int] :rtype: int """ result = 0 seats.sort() students.sort() save = [] for i in range(len(seats)): result += abs(seats[i]-students[i]) return result 复制代码
运行结果
Runtime: 61 ms, faster than 100.00% of Python online submissions for Minimum Number of Moves to Seat Everyone. Memory Usage: 13.4 MB, less than 100.00% of Python online submissions for Minimum Number of Moves to Sea
作者:王大呀呀
链接:https://juejin.cn/post/7019857217478213640