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

这道题到底在问什么

输入

seats=[3,1,5], students=[2,7,4]

输出

4

输入

seats=[2,2,6,6], students=[1,3,2,6]

输出

4

最优解：一步一步想明白

1. 3记牢这一句:两个数组各自排序,然后同名次配对,逐对累加绝对差。下面先把两排位置排好,再一对一对地算。
2. 4待排序先看座位这一排,原始顺序是 5、1、8、3、9、6,乱的。算法第一步是把它从小到大排好,这样名次就固定了,方便和学生一一对上。
3. 5升序完成排好之后座位变成 1、3、5、6、8、9,从左到右就是第 1 名到第 6 名座位。位置最小的排最左,最大的排最右。座位这边准备完毕。
4. 6待排序再看学生这一排,原始顺序是 2、7、4、1、6、3,也是乱的。同样地,把它从小到大排好,好和座位按名次对上。
5. 7升序完成排好之后学生变成 1、2、3、4、6、7,从左到右是第 1 名到第 6 名学生。两排都排好了,接下来就该把同名次的座位和学生凑成一对。
6. 8配对开始把两排放到一起看:上面主排是排好的座位 1、3、5、6、8、9,右侧栏是排好的学生 1、2、3、4、6、7。它们名次一一对齐,第 1 名座位对第 1 名学生,第 2 名对第 2 名,依此类推。现在累计移动是 0,咱们从第 1 名开始一对一对地算。
7. 9座位 1 ↔ 学生 1轮到第 1 名。紫色指到的座位在位置 1,侧栏高亮的第 1 名学生在位置 1。它俩要凑成一对,这名学生就往这个座位挪。这是开局第一对。
8. 10本对花费 0 · 累计 0算这一对的花费:座位 1 和学生 1 相差 0 格,这名学生原地就坐,一步都不用挪。把 0 加进累计,现在总数是 0。这一对搞定,染成绿色。
9. 11座位 3 ↔ 学生 2轮到第 2 名。紫色指到的座位在位置 3,侧栏高亮的第 2 名学生在位置 2。它俩要凑成一对,这名学生就往这个座位挪。前面 1 对已经配好,染成蓝色。
10. 12本对花费 1 · 累计 1算这一对的花费:座位 3 和学生 2 相差 1 格,这名学生挪 1 格就位。把 1 加进累计,现在总数是 1。这一对搞定,染成绿色。
11. 13座位 5 ↔ 学生 3轮到第 3 名。紫色指到的座位在位置 5,侧栏高亮的第 3 名学生在位置 3。它俩要凑成一对,这名学生就往这个座位挪。前面 2 对已经配好,染成蓝色。
12. 14本对花费 2 · 累计 3算这一对的花费:座位 5 和学生 3 相差 2 格,这名学生挪 2 格就位。把 2 加进累计,现在总数是 3。这一对搞定,染成绿色。
13. 15座位 6 ↔ 学生 4轮到第 4 名。紫色指到的座位在位置 6,侧栏高亮的第 4 名学生在位置 4。它俩要凑成一对,这名学生就往这个座位挪。前面 3 对已经配好,染成蓝色。
14. 16本对花费 2 · 累计 5算这一对的花费:座位 6 和学生 4 相差 2 格,这名学生挪 2 格就位。把 2 加进累计,现在总数是 5。这一对搞定,染成绿色。
15. 17座位 8 ↔ 学生 6轮到第 5 名。紫色指到的座位在位置 8,侧栏高亮的第 5 名学生在位置 6。它俩要凑成一对,这名学生就往这个座位挪。前面 4 对已经配好,染成蓝色。
16. 18本对花费 2 · 累计 7算这一对的花费:座位 8 和学生 6 相差 2 格,这名学生挪 2 格就位。把 2 加进累计,现在总数是 7。这一对搞定,染成绿色。
17. 19座位 9 ↔ 学生 7轮到第 6 名。紫色指到的座位在位置 9,侧栏高亮的第 6 名学生在位置 7。它俩要凑成一对,这名学生就往这个座位挪。前面 5 对已经配好,染成蓝色。
18. 20本对花费 2 · 累计 9算这一对的花费:座位 9 和学生 7 相差 2 格,这名学生挪 2 格就位。把 2 加进累计,现在总数是 9。这一对搞定,染成绿色。
19. 21总移动 9六对全部配好,整排染成绿色。逐对花费依次是 0、1、2、2、2、2,加起来正好 9 格。这就是排序后同名次配对得到的总移动次数。
20. 22原序配对 21为什么非要排序,看这个反例就懂了。如果不排序、直接按原始下标配对,座位 5 配学生 2、座位 1 配学生 7、座位 8 配学生 4,依此类推,逐对距离是 3、6、4、2、3、3,总共 21 格,比排序后的 9 足足多花 12 格。乱配会让小座位摊上远学生,白白多走路,排序正是为了避免这种交叉。
21. 23答案 = 9回放一遍。两排各自排序,同名次一一配对,逐对绝对差累加,最小总移动就是 0 加 1 加 2 加 2 加 2 加 2,等于 9。这就是让每名学生都坐上互不相同座位的最少移动次数,答案 9。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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))

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minMovesToSeat(vector<int>& seats, vector<int>& students) {
        sort(seats.begin(), seats.end());
        sort(students.begin(), students.end());
        int ans = 0;
        for (int i = 0; i < seats.size(); ++i) {
            ans += abs(seats[i] - students[i]);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int minMovesToSeat(int[] seats, int[] students) {
        Arrays.sort(seats);
        Arrays.sort(students);
        int ans = 0;
        for (int i = 0; i < seats.length; ++i) {
            ans += Math.abs(seats[i] - students[i]);
        }
        return ans;
    }
}

复杂度

面试官可能追问