首页 > 网易笔试8.8 第二题字典序
头像
offer到到到
编辑于 2020-08-08 17:41
+ 关注

网易笔试8.8 第二题字典序

package WangYi;

import java.util.HashSet;
import java.util.Scanner;
/*给定 n,再给了一个排列 T,扩充成排列 S(数字 1 - n 各使用一次)。问最小字典序的S
 * 一个T序列,长度为m,扩充为S序列,T为S的子序列,求最小字典序的S【长度为n】
 * 2 1 5===2 1 3 4 5
 * 1 对S序列扩充,得到2 1 5 3 4【填充的时候从1-n开始遍历,将不存在T的数字填充在S序列的后面,填充部分的数据肯定是小于n的,假如T为6 7 8则填充数据为1 2
 * 2 p1指向0,p1指向m,设置一个辅助数组,将3 4插入前面的合适位置
 */

public class Two {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int T[] = new int[m];
		HashSet<Integer> set = new HashSet<Integer>();
		int index = 0;
		int res[] = new int[n];
		for(int i = 0;i<m;i++) {
			T[i] = in.nextInt();
			res[index++] =T[i];
			if(!set.contains(T[i])) {
				set.add(T[i]);
			}
		}		
		for(int i = 1;i<=n;i++) {
			if(set.size()==n) break;
			if(!set.contains(i)) {
				set.add(i);
				res[index++] =i;
			}
		}
//		for (int i = 0; i < res.length; i++) {
//			System.out.println(res[i]);
//		}
		int p1 = 0;
		int p2 = m;
		int res1[] = new int[n];
		int p = 0;
		while(p1<m&&p2<n) {
			if(res[p1]<=res[p2]) {
				res1[p++] = res[p1++];
			}else {
				res1[p++] = res[p2++];
			}
		}
		while(p1<m) res1[p++] = res[p1++];
		while(p2<n) res1[p++] = res[p2++];
		for (int i = 0; i < res1.length; i++) {
			System.out.println(res1[i]);
	    }
	}

}

全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐