【每日一题Day73】LC2037使每位学生都有座位的最少移动次数 | 排序+贪心

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

使每位学生都有座位的最少移动次数【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 )
目录
打赏
0
0
0
0
5
分享
相关文章
|
9月前
【每日一题Day314】LC1921消灭怪物的最大数量 | 贪心+排序
【每日一题Day314】LC1921消灭怪物的最大数量 | 贪心+排序
66 0
|
9月前
【每日一题Day355】LC1402 做菜顺序 | 贪心+排序
【每日一题Day355】LC1402 做菜顺序 | 贪心+排序
61 0
LeetCode 2037. 使每位学生都有座位的最少移动次数
LeetCode 2037. 使每位学生都有座位的最少移动次数
225 0
LeetCode 2037. 使每位学生都有座位的最少移动次数
|
9月前
|
【每日一题Day310】LC1654到家的最少跳跃次数 | BFS
【每日一题Day310】LC1654到家的最少跳跃次数 | BFS
59 0
【每日一题Day95】LC1815得到新鲜甜甜圈的最多组数 | 状态压缩dp 记忆化搜索
子问题、哪些操作会影响数据:余下的甜甜圈数量left,以及剩余可以选的元素个数 cnt[x]【dfs函数的两个参数->使用状态压缩至一个int类型变量中】
125 0
【每日一题Day95】LC1815得到新鲜甜甜圈的最多组数 | 状态压缩dp 记忆化搜索
L1-049 天梯赛座位分配 (20 分)( for循环的深入理解+三维数组+错误分析)
L1-049 天梯赛座位分配 (20 分)( for循环的深入理解+三维数组+错误分析)
191 0
假币问题:有n枚硬币,其中有一枚是假币,已知假币的重量较轻。现只有一个天平,要求用尽量少的比较次数找出这枚假币。
(2)当n为奇数时,将前后两部分,即1…n,放在天平的两端,较轻的一端里有假币,继续在较轻的这部分硬币中用同样的方法找出假币;若两端重量相等,则中间的硬币,即第 (n+1)/2枚硬币是假币。n,放在天平的两端,较轻的一端里有假币,继续在较轻的这部分硬币中用同样的方法找出假币;假币问题:有n枚硬币,其中有一枚是假币,已知假币的重量较轻。:因为30位偶数,所以至少要被分一次,然后成为奇数之后,那个假币就是奇数的中位数,所以只需要2次。若输入的硬币数为30,则最少的比较次数为(2),最多的比价次数为(4)。
596 0
|
9月前
【错题集-编程题】活动安排(贪心 - 区间)
【错题集-编程题】活动安排(贪心 - 区间)
力扣(LeetCode)算法题解:1450. 在既定时间做作业的学生人数
力扣(LeetCode)算法题解:1450. 在既定时间做作业的学生人数
196 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等