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：

输入：seats = [2,2,6,6], students = [1,3,2,6]
输出：4

约束条件：

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

解题思路

这是一个经典的贪心算法问题。核心思想是通过排序来实现最优匹配。

思路分析：

  1. 贪心策略：为了使总移动次数最少，我们应该让位置最小的学生坐到位置最小的座位上，位置第二小的学生坐到位置第二小的座位上，以此类推。

  2. 证明贪心正确性：假设最优解中存在交叉匹配（即位置较小的学生被分配到位置较大的座位，位置较大的学生被分配到位置较小的座位），我们总可以通过交换这两个分配来减少总移动次数，因此贪心策略是正确的。

  3. 算法步骤：

    • 对座位数组和学生数组分别进行排序
    • 按顺序计算每个学生到对应座位的距离（绝对值差）
    • 累加所有距离得到最小移动次数

这种方法的时间复杂度主要来自排序操作，空间复杂度为常数级别（不考虑排序的额外空间）。

推荐解法：排序 + 贪心匹配（最优解）

代码实现

class Solution {
public:
    int minMovesToSeat(vector<int>& seats, vector<int>& students) {
        sort(seats.begin(), seats.end());
        sort(students.begin(), students.end());
        
        int moves = 0;
        for (int i = 0; i < seats.size(); i++) {
            moves += abs(seats[i] - students[i]);
        }
        
        return moves;
    }
};

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        seats.sort()
        students.sort()
        
        return sum(abs(seat - student) for seat, student in zip(seats, students))

public class Solution {
    public int MinMovesToSeat(int[] seats, int[] students) {
        Array.Sort(seats);
        Array.Sort(students);
        
        int moves = 0;
        for (int i = 0; i < seats.Length; i++) {
            moves += Math.Abs(seats[i] - students[i]);
        }
        
        return moves;
    }
}

/**
 * @param {number[]} seats
 * @param {number[]} students
 * @return {number}
 */
var minMovesToSeat = function(seats, students) {
    seats.sort((a, b) => a - b);
    students.sort((a, b) => a - b);
    
    let moves = 0;
    for (let i = 0; i < seats.length; i++) {
        moves += Math.abs(seats[i] - students[i]);
    }
    
    return moves;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要来自对两个数组的排序操作
空间复杂度O(1)只使用了常数级别的额外空间（不考虑排序的额外空间）