S 是 T 的子序列,当且仅当 S 是 T 通过删除任意数量元素所得到的.
字典序是单词在字典中的排列顺序,先比较第一个字母,然后比较第二个字母,依次类推。
第一行输入两个正整数 n 和 m.第二行输入 m 个数,表示输入序列 T1<= m <= n <= 100000
输出一行表示答案(注意处理行末空格)
5 3 2 1 5
2 1 3 4 5
5 2 4 2
1 3 4 2 5
简单点,set集合实现
import java.util.Scanner; import java.util.Set; import java.util.Arrays; import java.util.HashSet; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), m = sc.nextInt(); int[] T = new int[m]; int[] S = new int[n]; Set<Integer> set = new HashSet<>(); for(int i=0; i<m; i++) { T[i] = sc.nextInt(); set.add(T[i]); } int i=0, j=0; for(int k=0, l=1; k<(n-m) || j<m; ) { while(set.contains(l)) l++; if(j < m && l >= T[j]) S[i++] = T[j++]; else if(k<(n-m)) { S[i++] = l++; k++; } } Arrays.stream(S) .forEach(o -> System.out.print(o + " ")); } }
#include <bits/stdc++.h> using namespace std; class node { public: node *next; int val; node(int val): val(val), next(nullptr) {} }; int main() { int n, m; cin >> n >> m; unordered_map<int, int> mp; node *head = new node(-1); head->next = nullptr; node *temp = head; for (int i = 0; i < m; i++) { int num; cin >> num; temp->next = new node(num); temp = temp->next; mp[num] = 1; } int ind = 1; node *now = head->next, *prev = head; while (ind <= n) { if (!mp.count(ind)) { while (now && ind > now->val) { prev = now; now = now->next; } if (prev->next) { node *tmp = new node(ind); tmp->next = now; prev->next = tmp; prev = prev->next; } else { node *tmp = new node(ind); prev->next = tmp; now = tmp; } } ind++; } node *tmp = head->next; for (int i = 0; i < n && tmp; i++) { cout << tmp->val; tmp = tmp->next; i < n - 1 && cout << " "; } return 0; }
import java.util.*; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); int m = input.nextInt(); List<Integer> fix = new ArrayList<>(); List<Integer> free = new ArrayList<>(); boolean[] v = new boolean[n + 1]; for (int i = 0; i < m; i++) { int tmp = input.nextInt(); v[tmp] = true; fix.add(tmp); } for (int i = 1; i <= n; i++) if (!v[i]) free.add(i); //Collections.sort(fix); //Collections.sort(free); int i = 0; int j = 0; //String sm = ""; List<Integer> ans = new ArrayList<>(); while (i < free.size() && j < fix.size()) { //String s1 = sm + free.get(i); //String s2 = sm + fix.get(j); if (free.get(i) <= fix.get(j)) { ans.add(free.get(i++)); //sm = s1; } else { ans.add(fix.get(j++)); //sm = s2; } } while (i < free.size()) { ans.add(free.get(i++)); } while (j < fix.size()) { ans.add(fix.get(j++)); } for (i = 0; i < n; i++) { if (i == 0) System.out.print(ans.get(i)); else System.out.print(" " + ans.get(i)); } System.out.println(); } }
//题目感觉没说清楚,实际上所求的排列应该是“包含1~n的所有数且每个数仅出现一次” //语言:C++ #include <iostream> #include <unordered_set> #include <vector> using namespace std; int main() { int n,m; cin>>n>>m; unordered_set<int> use; vector<int> v(m); for(int i=0;i<m;i++) { cin>>v[i]; use.insert(v[i]); } vector<int> ret; int num=1; for(int i=0;i<v.size();i++) { while(num<v[i]) { if(use.find(num)==use.end()) { ret.push_back(num); use.insert(num); } num++; } ret.push_back(v[i]); } for(int i=ret.size()+1;i<=n;i++) ret.push_back(i); for(int i=0;i<ret.size();i++) { cout<<ret[i]; if(i<ret.size()-1) cout<<' '; } return 0; }
#include <iostream> #include <vector> #include <set> using namespace std; int main() { int n , m; cin >> n >> m; vector<int> vt(m); vector<int> vt1; vector<int> res(n); set<int> s; int index = 0; int index1 = 0; int index2 = 0; for(int i = 0;i < m;i++) { cin >> vt[i]; s.insert(vt[i]); } for(int i = 1;i <= n;i++) { if(!s.count(i)) vt1.push_back(i); } while(index < m && index1 < n - m) { if(vt[index] < vt1[index1]) { res[index2++] = vt[index++]; } else { res[index2++] = vt1[index1++]; } } while(index < m) res[index2++] = vt[index++]; while(index1 < n - m) res[index2++] = vt1[index1++]; for(int i = 0;i < n;i++) cout<<res[i]<< " "; return 0; }
#include<cstdio> #include<vector> #include<algorithm> #include<iostream> using namespace std; int main() { int n, m; scanf("%d %d", &n, &m); // 这题目是啥意思?长度为n的序列是值从1-n vector<int> vt(m, 0); //存放输入序列 vector<int> rs(n+1, 0); //临时序列 vector<int> st(n+1, 0); //存放结果 /* for (int i=0; i<=n; i++) { printf("%d ", st[i]); } */ for (int i=0; i<m; i++) { scanf("%d", &vt[i]); //接收输入的序列 rs[vt[i]]=-1; //表示这个值被使用了 } //然后其实就是把没有被使用的值插入放到原先的序列中,原先的序列位置在哪里会使得最小?? int index=1; //临时序列的下标 int cur=1; //结果序列下标 int i=0; while(cur<=n){ int ans=vt[i]; //如果临时序列中这个数没有在T中,且比当前的ans小,那就放到ans前面,一个萝卜一个坑 if(rs[index]==0 && index<ans){ st[cur++]=index++; if(index>n) break; } else if(rs[index]==0 && index>ans){ st[cur++]=ans; i++; if(i>=m) break; } else if(rs[index]==-1){ index++; if(index>n) break; } } while(cur<=n){ if(i<m) st[cur++]=vt[i++]; else if(index<=n) st[cur++]=index++; } for (int i=1; i<n; i++) { printf("%d ", st[i]); } printf("%d\n", st[n]); return 0; }