泡泡的课堂小练习之那些插队的人

题目简述

题目背景：

随着社会整体素质的提高，插队的现象已经越来越少了。但是仍旧有一个特殊情况，需要对于某些人进行优先处理。当这些人完成了自己插队的壮举之后，队伍的形态就变得千变万化。这个时候，得知每个人在哪里就变得尤为重要的，聪明的你一定可以完成这个艰巨的任务的，加油吧！

简明题意：

你有一个长度为 n 的队伍，从左到右依次为 1~n，有 m 次插队行为，用数组 cutIn 进行表示，cutIn 的元素依次代表想要插队的人的编号，每次插队，这个人都会直接移动到队伍的最前方。你需要返回一个整数，代表这 m 次插队行为之后，有多少个人已经不在原来队伍的位置了。

示例

输入
3,[3, 2, 3]
返回值
2
说明
初始队伍为 [1, 2, 3]
3 开始插队 [3, 1, 2]
2 开始插队 [2, 3, 1]
3 开始插队 [3, 2, 1]
所以2还在原来的尾置，3和1两个人已经不在原来的位置了

代码部分

暴力解法

    /*** 计算有多少个人最终不在自己原来的位置上* @param n int整型 队伍总长* @param cutIn int整型vector 依次会插队到最前方的人的编号* @return int整型*/int countDislocation(int n, vector<int>& cutIn){//检测,当cutIn为0是表示没有人插队//当n<=1时表示只有1个人，无法插队if (cutIn.size() == 0 || n <= 1){return 0;}//给定一个v1记录1-n同时赋值vector<int> v1(n,0);for(int i=0;i<n;i++){v1[i]=i+1;}//给定一个v2复制一份v1的值用来跟对比后的v1进行比较记录vector<int> v2(v1);//遍历cutIn 同时删除v1中的该数然后将该数插入v1的开头for(int x:cutIn){int a=v1[x-1];v1.erase(v1.begin()+x-1);v1.insert(v1.begin(),a);}//用来记录不在原来的位置上的人数int count=0;//当v1和v2该位置上的数不同时，表示该人不在原来的位置上了for(int i=0;i<n;i++){if(v1[i] != v2[i])count++;}return count;}

备注:

1. 如上代码比价容易让人理解，但缺点也很明显。内存超限
2. 而且需要遍历同一个vector容器多次
   

改良版

• 通过上面的代码知道，该题目无法进行暴力解法。
• 那么通过规律我们可以知道，只要我们找到cutIn中的最大的一个数max。
• 那么就可以知道max-n这之间的数都没有发生过位置的改变
• 那么就可以得到如下的代码

    int countDislocation(int n, vector<int>& cutIn) {if (cutIn.size() == 0 || n <= 1){return 0;}//记录cutIn中的最大值int max=0;//遍历cutIn,通过比较当前值与max的大小去保留最大值for(int x:cutIn){max=x>max?x:max;}//创建一个max大小的容器，max-n之间的值直接舍去vector<int> v1(max,0);//赋值for(int i=0;i<max;i++){v1[i]=i+1;}//移动for(int x:cutIn){int a=v1[x-1];v1.erase(v1.begin()+x-1);v1.insert(v1.begin(), a);}//计数int count=0;for(int i=0;i<max;i++){if(v1[i] != 1+i)count++;}return count;

备注：

1. 改方法略微简化了移动的操作复杂度从（n减小到了max）
2. 但当max=n时复杂度还是跟暴力破解一样
3. 其次，该方法也存在内存超限，需要进一步修改

终版

• 通过改良版我们舍去了不会变动的max-n的部分，那么有没有方法能进一步舍去更多的部分来达到精简的目的呢
• 通过规律我们发现，每一个插队的人的位置，跟其最后一次插队有关。
• 例如：2 5 1 2 那么2是在第一位，那么顺序遍历的第一个2就没有实际用处了，那么是不是可以直接跳过
• 那么我们是否能通过反向遍历来实现呢，如果一个数第复数次出现，那么就跳过这个数。
• 由此的到的最终版

int countDislocation(int n, vector<int>& cutIn)
{if (cutIn.size() == 0 || n <= 1){return 0;}//检测容器,用来存放第一次出现的数set<int> s1;//存放容器,用来存放所有人插完队后，插队人的容器vector<int> v1;int max=1;//反向遍历，从size（）-1 至 0for(int i=cutIn.size()-1;i>=0;i--){//定义一个数，接受cutIn的值int index=cutIn[i];//如果find函数没找到该值那么会返回容器末的end（）迭代器//证明未找到该数if(s1.find(index) == s1.end()){//s1容器中添加该数s1.insert(index);//将该数导入v1容器中v1.push_back(index);//比较记录最大值max=index>max?index:max;}}//定一个int变量记录不在原来位置的认输//因为假设5次插队（2,5,4,7,5）.//那么max为7,队列为5,7,4,2,1,3,6//那么1,3,6是不是直接挪到后面去了根本不需要去验证//即只需要验证前面4个数是否还在原来位置上int ret=max;for(int i=0;i<v1.size();i++){//如果该数还在原来位置上，那么计数器减一if(v1[i] == i+1){ret--;}}return ret;
}

• 该方法相较于前两个版本，极大缩减了所需要遍历的内容，也减少了创建一个队（记录所有人位置）的容器的时间。
• 精简了对比的时间，无需进行较多无意义的对比。