首页 > 试题广场 >

那些插队的人

[编程题]那些插队的人
  • 热度指数：3991 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
你有一个长度为 n 的队伍，从左到右依次为 1~n，有 m 次插队行为，用数组 cutIn 进行表示，cutIn 的元素依次代表想要插队的人的编号，每次插队，这个人都会直接移动到队伍的最前方。你需要返回一个整数，代表这 m 次插队行为之后，有多少个人已经不在原来队伍的位置了。
示例1

输入

3,[3, 2, 3]

输出

2

说明

初始队伍为 [1, 2, 3]
3 开始插队 [3, 1, 2]
2 开始插队 [2, 3, 1]
3 开始插队 [3, 2, 1]
所以2还在原来的尾置，3和1两个人已经不在原来的位置了。
示例2

输入

3,[]

输出

0

说明

没有人进行插队，所有人都在自己原来的位置上。

备注:
对于所有数据，保证 , ，且
算法知识视频讲解
开通博客
头像 Anoxiacxy
发表于 2020-02-05 18:59:39
题意 你有一个长度为 n 的队伍，从左到右依次为 1~n，有 m 次插队行为，用数组 cutIn 进行表示，cutIn 的元素依次代表想要插队的人的编号，每次插队，这个人都会直接移动到队伍的最前方。你需要返回一个整数，代表这 m 次插队行为之后，有多少个人已经不在原来队伍的位置了。 题解 如何写一份 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 进击的码虫
发表于 2020-03-27 22:24:38
本题在于理解插队的过程： 插队是插到队首，且可以多次插队，也就是说假如某人多次插队以最后一次插队为其最终位置，也就是将cutIn数组，倒着遍历（去重），则得到插队人员最后排列的队形；同时若A插队，A之前的所有不插队人员，均不能在其原来位置，故在插队数组中，最大插队的数字（即排在队伍最后的插队者），其 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Maokt
发表于 2021-07-30 13:22:35
算法思想一：遍历 解题思路： 可分为没插过队的和插过队的两种，最后的排队，没插过队的都在后面，插过队的最大值是个分界线。没插过队的小于这个分界线最后一定不在原来的位置，大于的一定在原来位置，插过队的，我们从后往前看，删除重复的，就是排队序列直接统计插过队的还在原来位置上的人数即可 代码展示： Pyt 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 CroMarmot
发表于 2021-10-02 19:24:33
题意 初始长度为nnn的数组aaa,值也是1~n即ai=ia_i=iai​=i 给定另一个操作数组cutIncutIncutIn表示对上述数组的更改，每次在aaa中找到值为cutInicutIn_icutIni​的，将这个值放到数组aaa的起始位置 求最终数组aaa中，位置和初始位置不同的有多少个 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 FrankKong
发表于 2020-10-28 19:54:57
其中n <= 1e9，创建数组进行模拟插队会超内存，不可行。只能找规律。 我们可以从cutIn中找到编号的最大值，在他之后的队伍没有参与插队，位置不变 cutIn中会存在通过插队还在原来位置上的人，将cutIn倒序，且去重，就是最终的前len个人 class Solution { publ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 进击的乾巧
发表于 2020-05-14 18:48:05
关键点都在代码注释里了 package main /** * 计算有多少个人最终不在自己原来的位置上 * @param n int整型 队伍总长 * @param cutIn int整型一维数组 依次会插队到最前方的人的编号 * @return int整型 */ func coun 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 认认真真coding
发表于 2021-07-31 16:31:28
题目描述你有一个长度为 n 的队伍，从左到右依次为 1~n，有 m 次插队行为，用数组 cutIn 进行表示，cutIn 的元素依次代表想要插队的人的编号，每次插队，这个人都会直接移动到队伍的最前方。你需要返回一个整数，代表这 m 次插队行为之后，有多少个人已经不在原来队伍的位置了。 方法一：遍历的 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 球球了给孩子一个offer吧
发表于 2021-08-02 17:10:24
题意：你有一个长度为 n 的队伍，从左到右依次为 1~n，有 m 次插队行为，用数组 cutIn 进行表示，cutIn 的元素依次代表想要插队的人的编号，每次插队，这个人都会直接移动到队伍的最前方。你需要返回一个整数，代表这 m 次插队行为之后，有多少个人已经不在原来队伍的位置了。示例 输入：3, 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-07-30 17:58:54
思路： 题目的主要信息： 长度为n为队伍，人员编号1-n cutIn数组中是要插队的编号，依次进行插队，即加入到最前面 求最后有多少人不在原来的位置 方法一：哈希表具体做法：对于最后的队列，没有插过队的人肯定都排在后面，最大插队元素是其分界线，最大插队元素之前的位置都可能有改变，之后的就不会有变 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛一霸
发表于 2021-07-31 22:59:39
题目：那些插队的人描述：你有一个长度为 n 的队伍，从左到右依次为 1~n，有 m 次插队行为，用数组 cutIn 进行表示，cutIn 的元素依次代表想要插队的人的编号，每次插队，这个人都会直接移动到队伍的最前方。你需要返回一个整数，代表这 m 次插队行为之后，有多少个人已经不在原来队伍的位置了。 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

数组 模拟
难度：
7条回答 3921浏览

热门推荐

通过挑战的用户

查看代码

相关试题

那些插队的人

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号