题目描述
思路解析动画文字版
记牢这一句:两个数组各自排序,然后同名次配对,逐对累加绝对差。下面先把两排位置排好,再一对一对地算。
座位 · 排序前：先看座位这一排,原始顺序是 5、1、8、3、9、6,乱的。算法第一步是把它从小到大排好,这样名次就固定了,方便和学生一一对上。
座位 · 排序后：排好之后座位变成 1、3、5、6、8、9,从左到右就是第 1 名到第 6 名座位。位置最小的排最左,最大的排最右。座位这边准备完毕。
学生 · 排序前：再看学生这一排,原始顺序是 2、7、4、1、6、3,也是乱的。同样地,把它从小到大排好,好和座位按名次对上。
学生 · 排序后：排好之后学生变成 1、2、3、4、6、7,从左到右是第 1 名到第 6 名学生。两排都排好了,接下来就该把同名次的座位和学生凑成一对。
两排对齐 · 准备配对：把两排放到一起看:上面主排是排好的座位 1、3、5、6、8、9,右侧栏是排好的学生 1、2、3、4、6、7。它们名次一一对齐,第 1 名座位对第 1 名学生,第 2 名对第 2 名,依此类推。现在累计移动是 0,咱们从第 1 名开始一对一对地算。
第 1 对 · 读取：轮到第 1 名。紫色指到的座位在位置 1,侧栏高亮的第 1 名学生在位置 1。它俩要凑成一对,这名学生就往这个座位挪。这是开局第一对。
第 1 对 · 结算：算这一对的花费:座位 1 和学生 1 相差 0 格,这名学生原地就坐,一步都不用挪。把 0 加进累计,现在总数是 0。这一对搞定,染成绿色。
第 2 对 · 读取：轮到第 2 名。紫色指到的座位在位置 3,侧栏高亮的第 2 名学生在位置 2。它俩要凑成一对,这名学生就往这个座位挪。前面 1 对已经配好,染成蓝色。
第 2 对 · 结算：算这一对的花费:座位 3 和学生 2 相差 1 格,这名学生挪 1 格就位。把 1 加进累计,现在总数是 1。这一对搞定,染成绿色。
第 3 对 · 读取：轮到第 3 名。紫色指到的座位在位置 5,侧栏高亮的第 3 名学生在位置 3。它俩要凑成一对,这名学生就往这个座位挪。前面 2 对已经配好,染成蓝色。
第 3 对 · 结算：算这一对的花费:座位 5 和学生 3 相差 2 格,这名学生挪 2 格就位。把 2 加进累计,现在总数是 3。这一对搞定,染成绿色。
第 4 对 · 读取：轮到第 4 名。紫色指到的座位在位置 6,侧栏高亮的第 4 名学生在位置 4。它俩要凑成一对,这名学生就往这个座位挪。前面 3 对已经配好,染成蓝色。
第 4 对 · 结算：算这一对的花费:座位 6 和学生 4 相差 2 格,这名学生挪 2 格就位。把 2 加进累计,现在总数是 5。这一对搞定,染成绿色。
第 5 对 · 读取：轮到第 5 名。紫色指到的座位在位置 8,侧栏高亮的第 5 名学生在位置 6。它俩要凑成一对,这名学生就往这个座位挪。前面 4 对已经配好,染成蓝色。
第 5 对 · 结算：算这一对的花费:座位 8 和学生 6 相差 2 格,这名学生挪 2 格就位。把 2 加进累计,现在总数是 7。这一对搞定,染成绿色。
第 6 对 · 读取：轮到第 6 名。紫色指到的座位在位置 9,侧栏高亮的第 6 名学生在位置 7。它俩要凑成一对,这名学生就往这个座位挪。前面 5 对已经配好,染成蓝色。
第 6 对 · 结算：算这一对的花费:座位 9 和学生 7 相差 2 格,这名学生挪 2 格就位。把 2 加进累计,现在总数是 9。这一对搞定,染成绿色。
全部配对完成：六对全部配好,整排染成绿色。逐对花费依次是 0、1、2、2、2、2,加起来正好 9 格。这就是排序后同名次配对得到的总移动次数。
反例 · 不排序更亏：为什么非要排序,看这个反例就懂了。如果不排序、直接按原始下标配对,座位 5 配学生 2、座位 1 配学生 7、座位 8 配学生 4,依此类推,逐对距离是 3、6、4、2、3、3,总共 21 格,比排序后的 9 足足多花 12 格。乱配会让小座位摊上远学生,白白多走路,排序正是为了避免这种交叉。
回放 · 答案 9：回放一遍。两排各自排序,同名次一一配对,逐对绝对差累加,最小总移动就是 0 加 1 加 2 加 2 加 2 加 2,等于 9。这就是让每名学生都坐上互不相同座位的最少移动次数,答案 9。
三个边界:普通例合计 4、含重复位置合计 4、单人同位置为 0,排序配对都成立。
面试重点:交换论证证同序最优、本质是一维绝对差最小权匹配、瓶颈在排序 O(n log n)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def minMovesToSeat(self, seats: List[int], students: List[int]) -> int: seats.sort() students.sort() return sum(abs(a - b) for a, b in zip(seats, students))复杂度
- 时间：O(n log n)，两次排序各是 O(n log n),之后一趟线性扫描配对累加是 O(n),整体由排序主导,记 O(n log n)
- 空间：O(1) 或 O(n)，除排序外只用常数个变量存累计和,是 O(1)。排序自身的额外开销分语言:C plus plus 与 Java 的排序递归栈约 O(log n),Python 的 Timsort 最坏 O(n),若把排序开销计进去以此为准
易错点
面试追问把动画讲成自己的话
追问为什么两边排序后同名次配对就是最优?
追问这题和用最小费用最大流做二分图最优匹配有什么关系?
追问复杂度是多少,瓶颈在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
拆分数位后四位数字的最小和
LeetCode 2160 · 简单 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题