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

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.

元旦快乐啦

• 思路：要使总移动次数最少，那么要将每个学生移动至离其最近的座位，因此将座位和学生的位置进行升序排序，每个学生需要的移动次数即为对应位置相减，累加返回最终结果

• 实现

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

。复杂度

• 时间复杂度：O ( n )
• 空间复杂度：O ( 1 )

• 实现

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

。复杂度

• 时间复杂度：O ( n )
• 空间复杂度：O ( 1 )