序列操作

[编程题]序列操作

热度指数：2648 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一天你得到了一个长度为 n 的序列，序列中的元素分别是 1,2,3,...,n。接下来你想对这个序列进行一些操作。每一次操作你会选择一个数然后将它从序列中原来的位置取出并放在序列的最前面。你想知道经过一系列操作后这个序列长什么样。

数据范围： $1 \le k_i \le n,m \le 10^5 \$

输入描述:

第一行包含两个整数 𝑛, 𝑚，分别表示序列的长度和操作的个数。
接下来 𝑚 行每行包含一个整数 𝑘𝑖 ，表示你要把 𝑘𝑖 放到序列的最前面。

输出描述:

从前往后输出序列中的每个元素，每个元素占一行。

示例1

输入

输出

说明

初始时序列为 1,2,3,4,5，经过第一次操作后序列为 4,1,2,3,5，经过第二次操作后序列为
2,4,1,3,5，经过第三次操作后序列为 5,2,4,1,3。

算法知识视频讲解

Java

洋葱入侵

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)

Java

Mono_Chrome

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)