有一天你得到了一个长度为 n 的序列，序列中的元素分别是 1,2,3,...,n。接下来你想对这个序 列进行一些操作。每一次操作你会选择一个数然后将它从序列中原来的位置取出并放在序列 的最前面。你想知道经过一系列操作后这个序列长什么样。
数据范围： 
[编程题]序列操作
- 热度指数：2648 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行包含两个整数 𝑛, 𝑚，分别表示序列的长度和操作的个数。接下来 𝑚 行每行包含一个整数 𝑘𝑖 ，表示你要把 𝑘𝑖 放到序列的最前面。
输出描述:
从前往后输出序列中的每个元素，每个元素占一行。
示例1
输入
5 3 4 2 5
输出
5 2 4 1 3
说明
初始时序列为 1,2,3,4,5，经过第一次操作后序列为 4,1,2,3,5，经过第二次操作后序列为
2,4,1,3,5，经过第三次操作后序列为 5,2,4,1,3。
# 插入排序的思路，只是不比较数值的大小，而是强调操作的顺序 # remove(value) 根据值删除list元素 # insert(index, value) 在指定索引位置插入元素 # insert()和remove()时间复杂度过高，在这道题目里不适用 n, m = map(int, input().split()) ln = [0 for i in range(n+1)] # 用于统计那个位置做了变化 lt = [] for j in range(m): t = int(input()) lt.append(t) # 存在重复移动同一个元素的情况 for e in lt[::-1]: # list切片逆序写法不熟练 if ln[e] == 0: print(e) ln[e] = 1 for e in range(1, n+1): if ln[e] == 0: print(e) # 看似简单的题目，有很多情况想的不够仔细，特别是忽略了可能存在重复把一个元素移动到开头的情况
发表于 2019-08-11 19:34:45
回复(1)
1.将移动过的数字压入栈中，然后对栈中数字进行弹栈打印。值得注意的是，我们在弹出数字时（越先被弹出的数字就是越后被移动过的数字），需要标记这个数字是否已经被弹出过，如果发现这个数字已经被弹出过，说明这个数字被移动过不止一次，以最后一次移动为准，忽略这个重复的数字，否则打印该数字。
2.遍历1~n，跳过被移动的数字，未被移动的数字应该保持之前的顺序不变，按原始顺序打印。
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] used = new int[n + 1];
// 先将要移动的数存到栈中
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < m; i++) stack.push(sc.nextInt());
while(!stack.isEmpty()){
int num = stack.pop();
if(used[num] == 0){
// 这个数还没有被移动过，直接打印
System.out.println(num);
// 将其标记为移动过
used[num] = 1;
}
}
for(int num = 1; num <= n; num++)
if(used[num] == 0) System.out.println(num);
}
}
发表于 2021-02-15 13:46:26
回复(0)
1.优化内存结构，降低内存占用
用占用量更小的boolean数组存储数字标识；去重；
用int数组替代stack，反转；
2.优化执行时间
尽量避免引用更多的外部类增加类加载时间；
将Scanner、BufferedReader、BufferedInputStream等替换为原生io操作、直接解析读入的数字；
先组合String，后统一输出
import java.io.InputStream;
import java.util.Stack;
public class Main {
public static int next(InputStream in) throws Exception {
StringBuilder sb = new StringBuilder();
char c;
while (true) {
c = (char) in.read();
if (c != '\n' && c != ' ') {
sb.append(c);
} else {
break;
}
}
return Integer.parseInt(sb.toString());
}
public static void main(String[] args) throws Exception {
int m = next(System.in) + 1;
int n = next(System.in);
boolean[] flags = new boolean[m];
int[] stack = new int[n];
for (int i = 0; i < n; i++) {
int c = next(System.in);
stack[n - i - 1] = c;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
int val = stack[i];
if (!flags[val]) {
sb.append(val).append("\n");
flags[val] = true;
}
}
for (int i = 1; i < m; i++) {
if (!flags[i]) {
sb.append(i).append("\n");
}
}
System.out.println(sb.toString());
}
}
发表于 2020-09-13 19:10:57
回复(0)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main()
{
int n, m;
cin>>n>>m;
vector<bool> nums(n+1, false);
stack<int> S;
for(int i=0;i<m;i++)
{
int x;
cin>>x;
S.push(x);
}
for(int i=0;i<m;i++)
{
int x = S.top();
S.pop();
if(nums[x]==false)
{
cout<<x<<endl;
nums[x] = true;
}
}
for(int i=1;i<=n;i++)
if(nums[i]==false)
cout<<i<<endl;
return 0;
}
编辑于 2020-08-11 17:09:11
回复(0)
#include<bits/stdc++.h>
using namespace std;
struct node//简历双向链表
{
int val;
node * pre;
node*next;
node(int v)
{
val = v;
next = NULL;
pre = NULL;
}
};
node *head;
unordered_map<int, node*>mp;//建立值与地址的映射
void update(int val)//通过获取对应值的地址来进行链表的处理
{
node * tmp = mp[val];
node *_pre = tmp->pre;
node *q = tmp->next;
_pre->next = q;
if(q)
q->pre = _pre;
q = head->next;
head->next = tmp;
tmp->pre = head;
tmp->next = q;
q->pre = tmp;
}
int main()
{
int n, m;
cin >> n >> m;
head = new node(-1);
node * p = head;
for (int i = 1; i <= n; i++)//构造初始链表
{
p->next = new node(i);
p->next->pre = p;
mp[i] = p->next;
p = p->next;
}
int tmp;
while (m--)
{
cin >> tmp;
update(tmp);
}
head = head->next;
while (head)
{
cout << head->val << endl;
head = head->next;
}
}
发表于 2020-06-13 20:34:35
回复(0)
用栈存储每次的输入值，因为也是逆序输出，所以只需要弹栈即可，弹出的时候做一下去重处理，栈内所有元素输出完后，输出没在栈内的其他数。
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main(void)
{
int len, count;
cin >> len >> count;
int temp_count = count;
vector<int> data(len + 1, 0);
stack<int> num;
while (temp_count--)
{
int temp;
cin >> temp;
num.push(temp);
data[temp] = 1;
}
while (!num.empty())
{
if (data[num.top()] == 1)
{
cout << num.top() << endl;
data[num.top()] = 2;
num.pop();
continue;
}
if (data[num.top()] == 2)
{
num.pop();
}
}
for (int i = 1; i <= len; i++)
{
if (data[i] == 0)
cout << i << endl;
}
return 0;
}
编辑于 2019-07-17 23:17:14
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i + 1;
}
int m = sc.nextInt();
Stack<Integer> stack = new Stack<>();
HashSet<Integer> set = new HashSet<>();
HashSet<Integer> setHelp = new HashSet<>();
while (m-- > 0) {
int cur = sc.nextInt();
set.add(cur);
stack.push(cur);
arr[cur - 1] = -1;
}
int times = set.size();
while (!stack.isEmpty()) {
if (times > 0) {
int temp = stack.pop();
if (!setHelp.contains(temp)) {
setHelp.add(temp);
System.out.println(temp);
times--;
}
} else {
break;
}
}
for (Integer num : arr) {
if (num != -1) {
System.out.println(num);
}
}
}
}
发表于 2019-06-16 14:31:19
回复(0)
//O(n)时间复杂度，倒序输出改动的，用一个数组标记已经输出的，再正序输出未输出的
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
while(scan.hasNext()) {
int n = scan.nextInt();
int m = scan.nextInt();
int[]data=new int[n+1];
int[]tem=new int[m];
for(int i=0;i<m;i++){
tem[i]=scan.nextInt();
}
for(int i=m-1;i>-1;i--){
int po=tem[i];
if(data[po]==0){
System.out.println(po);
data[po]=-1;
}
}
for(int i=1;i<n+1;i++){
if(data[i]==0){
System.out.println(i);
}
}
}
}
}
发表于 2019-05-08 20:55:55
回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
/**
* @author wylu
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] strs = br.readLine().split(" ");
int n = Integer.parseInt(strs[0]), m = Integer.parseInt(strs[1]);
boolean[] flag = new boolean[n + 1];
LinkedList<Integer> stack = new LinkedList<>();
for (int i = 0; i < m; i++) {
int k = Integer.parseInt(br.readLine());
stack.push(k);
flag[k] = true;
}
boolean[] visited = new boolean[n + 1];
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
int k = stack.pop();
if (!visited[k]) sb.append(k).append("\n");
visited[k] = true;
}
for (int i = 1; i <= n; i++) {
if (!flag[i]) sb.append(i).append("\n");
}
System.out.print(sb);
}
}
发表于 2019-03-13 13:38:09
回复(0)
#include <bits/stdc++.h>
using namespace std;
struct Node{ int val; Node* next;
};
int main()
{ int n,m; while(cin>>n>>m){ int a[n+m+1]; bool b[n+1]; memset(b,false,sizeof(b)); for(int i=1;i<=n;i++) a[i] = n+1-i; int t = n; for(int i=1;i<=m;i++){ cin>>a[++t]; } while(n--){ if(!b[a[t]]){ b[a[t]] = true; cout<<a[t--]<<endl; }else{ t--; n++; } } } return 0;
}
发表于 2019-02-20 03:36:22
回复(0)
import java.util.*;
public class Main {
private static int MAX = (int)1e5;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
int[] bitmap = new int[MAX / 32 + 5];
StringBuilder sb = new StringBuilder();
ArrayList<Integer> arr = new ArrayList<>();
for (int i=0; i!=m; i++) {
arr.add(sc.nextInt());
}
for (int i=m-1; i>=0; i--) {
int num = arr.get(i);
if (((bitmap[num/32] >> (num%32)) & 1) == 0) {
sb.append(num);
sb.append("\n");
bitmap[num/32] |= (1 << (num % 32));
}
}
for (int i=1; i<=n; i++) {
if (((bitmap[i/32] >> (i%32)) & 1) == 0) {
sb.append(i);
sb.append("\n");
}
}
System.out.print(sb.toString());
return;
}
}
发表于 2019-02-10 22:25:05
回复(0)
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int m = sc.nextInt();
sc.nextLine();
int[] operations = new int[m];
for (int i = 0; i < m; i++) {
operations[i] = sc.nextInt();
}
LinkedList<Integer> sequence = getSequence(operations, n);
for (Integer integer : sequence) {
System.out.println(integer);
}
}
}
public static LinkedList<Integer> getSequence(int[] operations, int n){
LinkedList<Integer> list = new LinkedList<>();
boolean[] used = new boolean[n+1];
//从后往前遍历operations，加入到数组中
for (int i = operations.length-1; i >= 0; i--) {
//如果该数在之前有加入到数组中，这一次操作是会被后面的操作覆盖的，所以说需要跳过这次操作
if (used[operations[i]]){
continue;
}
list.add(operations[i]);
used[operations[i]] = true;
}
for (int i = 1; i < used.length; i++) {
if (!used[i]){
list.addLast(i);
}
}
return list;
}
}
发表于 2022-03-16 02:46:08
回复(0)
思路：从交换序列的最后开始计算，得到每个交换数最后交换的位置，然后先输出逆序的交换序列再根据哈希查表输出为交换的值
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<int> v(n+1,0);
vector<int> res(m);
vector<int> temp;
for(int i=0;i<m;i++) cin>>res[i];
for(int i=m-1;i>=0;i--){
if(v[res[i]]==0){
temp.push_back(res[i]);
v[res[i]]=1;
}
}
for(int i=0;i<temp.size();i++) cout<<temp[i]<<endl;
for(int i=1;i<=n;i++){
if(v[i]==0) cout<<i<<endl;
}
return 0;
}
#include<vector>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<int> v(n+1,0);
vector<int> res(m);
vector<int> temp;
for(int i=0;i<m;i++) cin>>res[i];
for(int i=m-1;i>=0;i--){
if(v[res[i]]==0){
temp.push_back(res[i]);
v[res[i]]=1;
}
}
for(int i=0;i<temp.size();i++) cout<<temp[i]<<endl;
for(int i=1;i<=n;i++){
if(v[i]==0) cout<<i<<endl;
}
return 0;
}
发表于 2020-08-30 15:15:47
回复(0)
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n,m;
cin >> n>>m;
int *book=new int[n+1];
vector<int> v;
vector<int> w;
vector<int> s;
for(int i=0;i<n;i++)
v.push_back(i+1);
for(int i=0;i<n+1;i++)
book[i]=0;
for(int i=0;i<m;i++){
int tem;
cin >> tem;
w.push_back(tem);
}
for(int i=m-1;i>=0;i--){
if(book[w.at(i)]==0){
book[w.at(i)]=1;
s.push_back(w.at(i));
v.at(w.at(i)-1)=0;
}
else continue;
}
for(int i=0;i<s.size();i++)
cout << s.at(i) << endl;
for(int i=0;i<n;i++)
if(v.at(i)!=0) cout << v.at(i) << endl;
return 0;
}
#include <vector>
using namespace std;
int main()
{
int n,m;
cin >> n>>m;
int *book=new int[n+1];
vector<int> v;
vector<int> w;
vector<int> s;
for(int i=0;i<n;i++)
v.push_back(i+1);
for(int i=0;i<n+1;i++)
book[i]=0;
for(int i=0;i<m;i++){
int tem;
cin >> tem;
w.push_back(tem);
}
for(int i=m-1;i>=0;i--){
if(book[w.at(i)]==0){
book[w.at(i)]=1;
s.push_back(w.at(i));
v.at(w.at(i)-1)=0;
}
else continue;
}
for(int i=0;i<s.size();i++)
cout << s.at(i) << endl;
for(int i=0;i<n;i++)
if(v.at(i)!=0) cout << v.at(i) << endl;
return 0;
}
发表于 2020-06-09 21:06:21
回复(0)
#include<iostream>
#include<stack>
#include<map>
using namespace std;
int main()
{
int N,M;
cin>>N>>M;
stack<int> cs;
map<int,int> visited;
int temp;
for(int i=0;i<M;i++)
{
cin>>temp;
visited[temp]++;
cs.push(temp);
}
while(!cs.empty())
{
if(visited[cs.top()]>1)
{
cout<<cs.top()<<endl;
visited[cs.top()]=0;
}
if(visited[cs.top()]==1)
{
cout<<cs.top()<<endl;
}
cs.pop();
}
for(int i=0;i<N;i++)
{
if(visited.find(i+1)==visited.end()) cout<<i+1<<endl;
}
} 栈与关联容器的应用，注意标记相同元素多次入栈就行，
发表于 2019-09-10 22:37:11
回复(0)
import java.util.Scanner;
public clas***ain {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] b = new int[m];
for (int i = 0; i < m; i++) {
b[i] = scanner.nextInt();
}
int[] res = solve(n, b);
for (int i = 0; i < n; i++) {
System.out.println(res[i]);
}
}
private static int[] solve(int n, int[] b) {
int[] res = new int[n];
int index = 0;
boolean[] isRemove = new boolean[n];
for (int i = b.length - 1; i >= 0; i--) {
if (isRemove[b[i] - 1]) {
continue;
}
res[index++] = b[i];
isRemove[b[i] - 1] = true;
}
for (int j = 0; j < n; j++) {
if (isRemove[j]) {
continue;
}
res[index++] = j + 1;
}
return res;
}
}
编辑于 2019-05-22 14:10:37
回复(0)
n = list(int(n) for n in input().split(" "))
nn = list(range(1, n[0]+1))
for i in range(n[1]):
a = eval(input())
nn.remove(a)
nn.insert(0, a)
for i in nn:
print(i)
求解，这是算法复杂度过大吗？
发表于 2019-04-23 18:40:11
回复(0)
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int arr[100001],arr1[100001];
for(int i=1;i<=m;i++)
cin>>arr1[i];
int k=2;
arr[1]=arr1[m];
cout<<arr[1]<<endl;
for(int i=m-1;i>0;i--)
{
int flag=0;
for(int j=1;j<k;j++)
{
if(arr1[i]==arr[j])
{
flag=1;
break;
}
}
if(flag!=1)
{
arr[k]=arr1[i];
cout<<arr[k]<<endl;
k++;
}
}
sort(arr+1,arr+k);
int j=1;
for(int i=1;i<=n;i++)
{
if(i==arr[j])
{
if(j<m)
j++;
}
else
{
cout<<i<<endl;
}
}
}
纯数学算法：
1、按照倒序去重输出操作过的数；
2、按照正序输出未进行操作过的数。
发表于 2019-04-17 15:50:39
回复(0)
//分享一下彩笔解法，基本是按照题目叙述做的，时间和空间复杂度都不低。。。能改进的话，求告诉我
#include<vector>
#include<iostream>
#include<set>
#include<stdio.h>
using namespace std;
int main(){
int n,m;
while(scanf("%d%d",&n,&m )!=EOF){
set<int>data;
for(int i=1;i<=n;i++){
data.insert(i);
}
vector<int>c(m);
for(int i=0;i<m;i++){
scanf("%d",&c[i]);
if(data.count(c[i])){
data.erase(c[i]);
}
}
printf("%d\n",c[m-1]);
set<int>xx;
xx.insert(c[m-1]);
for(int i=c.size()-2;i>=0;i--){
bool cunzai = xx.count(c[i]);
xx.insert(c[i]);
if(!cunzai){
printf("%d\n",c[i]);
}
}
for(set<int>::iterator it=data.begin();it!=data.end();it++){
printf("%d\n",*it);
}
}
return 0;
}
发表于 2019-04-12 16:33:03
回复(0)
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,i,j,l;
int k[100000];
int h[200000];
memset(h,0,sizeof(h));
memset(k,0,sizeof(k));
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
{
h[i+m]=i;
}
for(i=0;i<m;i++)
{
scanf("%d",&k[i]);
if(h[m+k[i]]<=0)
{
l=-h[m+k[i]];
h[l]=0;
h[m-i]=k[i];
h[m+k[i]]=i-m;
}
else
{
h[m-i]=k[i];
h[m+k[i]]=i-m;
}
}
for(i=0;i<=m+n;i++)
{
if(h[i]>0)
{
printf("%d\n",h[i]);
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,i,j,l;
int k[100000];
int h[200000];
memset(h,0,sizeof(h));
memset(k,0,sizeof(k));
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
{
h[i+m]=i;
}
for(i=0;i<m;i++)
{
scanf("%d",&k[i]);
if(h[m+k[i]]<=0)
{
l=-h[m+k[i]];
h[l]=0;
h[m-i]=k[i];
h[m+k[i]]=i-m;
}
else
{
h[m-i]=k[i];
h[m+k[i]]=i-m;
}
}
for(i=0;i<=m+n;i++)
{
if(h[i]>0)
{
printf("%d\n",h[i]);
}
}
return 0;
}
发表于 2019-02-01 08:54:05
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
