LeetCode刷题集（二）（LeetCode 2037使每位学生都有座位的最少移动次数）

客官°小女子只卖身不卖艺 2023-09-30 23:18 119阅读 0赞

## 学习目标： ##

> 掌握LeetCode2037使每位学生都有座位的最少移动次数

--------------------

## 题目内容： ##

> 一个房间里有 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 移动到位置 4 ，移动 1 次。  
> 第三位学生从位置 2 移动到位置 5 ，移动 3 次。  
> 第四位学生从位置 6 移动到位置 9 ，移动 3 次。  
> 总共 0 + 1 + 3 + 3 = 7 次移动。

> 示例3、输入：seats = \[2,2,6,6\], students = \[1,3,2,6\]  
> 输出：4  
> 解释：学生移动方式如下：  
> 第一位学生从位置 1 移动到位置 2 ，移动 1 次。  
> 第二位学生从位置 3 移动到位置 6 ，移动 3 次。  
> 第三位学生不移动。  
> 第四位学生不移动。  
> 总共 1 + 3 + 0 + 0 = 4 次移动。

--------------------

## 题目分析时间： ##

> 首先我们一拿到本题，我们应该想象一下，本题的解题思路，我的思路是先把它排序一下，让他的顺序从小到大进行排序，那么如果我们用c语言如何对数组进行排序呢？我们要是手写一个排序的话时间复杂度肯定很高那么这个时候我们就想到了利用c语言中的库函数qsort，其底层是用快速排序来写的，时间复杂度极大的得到了提高，底下图片就是qsort的函数，那么我们已经把数据排序好了，这个时候是不是在用每个学生的数据进行相减就能解出来啦，对的没错！  
> ![在这里插入图片描述][174cb8dd068b453099ba1b0cf325c09e.png]  
> ![在这里插入图片描述][f3286ab55cae41aaaf064ad95c7e0bc3.png]

--------------------

## 代码产出： ##

int cmp(const void* s1,const void* s2)
    {
        
        return (*(int*)s1 - *(int*)s2);
    }
    
    int minMovesToSeat(int* seats, int seatsSize, int* students, int studentsSize){
        
        qsort(seats,seatsSize,sizeof(int),cmp);
        qsort(students,studentsSize,sizeof(int),cmp);
        int res = 0;
        for(int i = 0;i < studentsSize;i++)
        {
        
            res += (abs(seats[i] - students[i]));
        }
        return res;
    }

> 这里的abs是去绝对值的意思！好啦今日的分享结束啦！

[174cb8dd068b453099ba1b0cf325c09e.png]: https://img-blog.csdnimg.cn/174cb8dd068b453099ba1b0cf325c09e.png
[f3286ab55cae41aaaf064ad95c7e0bc3.png]: https://img-blog.csdnimg.cn/f3286ab55cae41aaaf064ad95c7e0bc3.png