首页 > 试题广场 >

那些插队的人

[编程题]那些插队的人
  • 热度指数：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

说明

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

备注:
对于所有数据，保证 , ，且
算法知识视频讲解
添加回答
notrp头像 notrp
显然，这题需要将插队序列倒过来处理，假设有一个人插了很多次队，那么最后一次插队才是他最终的位置。比如样例 15 [10,4,6,5,9,7,3,3,9,10] 根据插队序列模拟其最后排队形成过程：
  1. 10
  2. 10 9
  3. 10 9 3
  4. 10 9 3 7
  5. 10 9 3 7 5
  6. 10 9 3 7 5 6
  7. 10 9 3 7 5 6 4
  8. 10 9 3 7 5 6 4 1 2 3
对于插队序列中的每一个人，我们只需要考虑其最后一次插队即可。
接下来求解答案，插队序列中最大值为10， 那么大于等于10的部分队伍序列肯定都是对的，所以我们要找就是[1,10]这个区间有多少个人不在自己的位置上，可以反过来求[1,10]里有多少人在正确的位置上，因为能在正确的位置上出现的人，一定是属于插队序列里的人，所以我们可以比较插队后的位置和实际位置判断这个人是否在正确的位置。（不插队的话，肯定会被从原来的位置挤开，那么就不可能出出现在正确的位置） 
class Solution {
public:
    /**
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型vector 依次会插队到最前方的人的编号
     * @return int整型
     */
    int countDislocation(int n, vector<int>& cutIn) {
        // write code here
        map<int,int> vis;
        int cnt = 0,maxv = 0;
        int right = 0;
        for(int i = cutIn.size()-1; ~i; -- i) {
            if(!vis.count(cutIn[i]-1)) {
                vis[cutIn[i]-1] = 1;
                if(cutIn[i]-1 == cnt++) right ++;
                maxv = max(maxv,cutIn[i]);
            }
        }
        return maxv-right;
    }
};


发表于 2020-03-30 02:04:27 回复(2)
C/C++
nbgao头像 nbgao 
#include <unordered_map>
class Solution {
public:
    /**
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型vector 依次会插队到最前方的人的编号
     * @return int整型
     */
    int countDislocation(int n, vector<int>& cutIn) {
        unordered_map<int, bool> vis;
        int m=cutIn.size(), Max=0, cnt=0;
        for(int i=m-1,j=0;i>=0;i--){
            if(vis.find(cutIn[i]-1)==vis.end()){
                vis[cutIn[i]-1] = true;
                if(cutIn[i]-1 == j++)
                    cnt++;
                Max = max(Max, cutIn[i]);
            }
        }
        return Max - cnt;
    }
};

编辑于 2020-08-17 23:31:13 回复(0)
荒草浸风头像 荒草浸风

可分为没插过队的和插过队的两种

最后的排队，没插过队的都在后面

插过队的最大值是个分界线。

没插过队的小于这个分界线最后一定不在原来的位置，大于的一定在原来位置

插过队的，我们从后往前看，删除重复的，就是排队序列

直接统计插过队的还在原来位置上的人数即可。 
class Solution:
    def countDislocation(self , n , cutIn ):
        # write code here
        cd = set()
        m = len(cutIn)
        if m==0:
            print(0)
            return
        res = max(cutIn)
        for i in range(m-1,-1,-1):
            if cutIn[i] not in cd:
                if cutIn[i]==len(cd)+1:
                    res-=1
                cd.add(cutIn[i])
        
        return res


发表于 2020-04-11 17:30:57 回复(0)
.晚安头像 .晚安 
class Solution {
public:
    /**
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型vector 依次会插队到最前方的人的编号
     * @return int整型
     */
    int countDislocation(int n, vector<int>& cutIn) {
        vector<bool> a(n + 1, false);
        int Max = 0, A = 0, N = 0;
        for (int i = cutIn.size() - 1; i >= 0; i--) {
            if (!a[cutIn[i]]) {
                N += ++A == cutIn[i];
                a[cutIn[i]] = true;
                Max = max(Max, cutIn[i]);
            }
        }
        return Max - N;
    }
};

发表于 2020-07-26 16:52:51 回复(0)
萨巴鲁酱头像 萨巴鲁酱
第一种方法： 
class Solution {
public:
    /**
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型vector 依次会插队到最前方的人的编号
     * @return int整型
     */
    int countDislocation(int n, vector<int>& cutIn) {
        // write code here
        int res = 0, len = 0, MAX = -1;
        set<int> s;
        for(auto it = cutIn.rbegin(); it != cutIn.rend(); ++it){
            if(s.find(*it) == s.end()){
                MAX = max(MAX, *it);
                s.insert(*it);
                if(*it - len == 1)
                    res++;
                len++;
            }             
        }
        return MAX - res;
    }
};

第二种方法 
class Solution {
public:
    /**
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型vector 依次会插队到最前方的人的编号
     * @return int整型
     */
    int countDislocation(int n, vector<int>& cutIn) {
        // write code here
        int res = 0, len = 0, cnt = 0;
        set<int> s;
        vector<int> v;
        for(auto it = cutIn.rbegin(); it != cutIn.rend(); ++it){
            if(s.find(*it) == s.end()){
                s.insert(*it);
                v.push_back(*it);
                if(*it - len == 1)
                    res++;
                len++;
            }             
        }
        sort(v.begin(), v.end());
        for(int a : v)
            cout << a << " ";
        cout << endl;
        
        for(int i = 1, j = 0; j < v.size(); i = v[j] + 1, j++){
            for(int k = i; k < v[j]; ++k){
                if(k - len == 1)
                    res++;
                len++;
            }
        }
        for(int k = v[v.size()-1] + 1; k <= n; ++k){
            if(k - len == 1)
                res++;
            len++;
        }
        return n - res;
    }
};


发表于 2020-05-19 01:33:30 回复(0)
Python
小哈20191023081480头像 小哈20191023081480
为什么我只能评论25个字以内 
class Solution:
    def countDislocation(self , n , cutIn ):
        if len(cutIn) == 0:
            return 0
        nn = max(cutIn)
        cutIn.reverse()
        cut = sorted(set(cutIn), key=cutIn.index)
        sums = 0
        for index, value in enumerate(cut):
            if index + 1 == value:
                sums += 1
        return nn - sums


发表于 2020-05-14 03:07:44 回复(0)
offerPlusPlus_头像 offerPlusPlus_ 
import java.util.*;


public class Solution {
    /**
     * 计算有多少个人最终不在自己原来的位置上
     * @param n int整型 队伍总长
     * @param cutIn int整型一维数组 依次会插队到最前方的人的编号
     * @return int整型
     */
    public int countDislocation (int n, int[] cutIn) {
        // write code here
        if(cutIn.length==0){
            return 0;
        }
        int len=cutIn.length;
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        int index=1;
        int max=Integer.MIN_VALUE;
        for (int i = len-1; i >=0 ; i--) {
            max=max>cutIn[i]?max:cutIn[i];
            if(!map.containsKey(cutIn[i])){
                map.put(cutIn[i],index++);
            }
        }
        int num=0;
        for(Integer key : map.keySet()){
            if(map.get(key)!=key){
                num++;
            }
        }
        num+=(n-map.size())-(n-max);
        return num;
    }
}

发表于 2020-03-27 15:57:11 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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