题解 | #【模板】序列操作#

题目链接

题目描述

你需要维护一个初始为空的整数序列，并根据指令执行相应的操作。总共有 8 种操作：

1 x: 在序列末尾添加整数 x。
2: 删除序列末尾的元素。
3 i: 查询并输出序列中下标为 i 的元素。
4 i x: 在下标为 i 的元素之后插入整数 x。
5: 将序列升序排序。
6: 将序列降序排序。
7: 输出序列的当前长度。
8: 输出整个序列。

解题思路

这道题是典型的数据结构模拟题，要求我们使用合适的数据结构来高效地维护一个动态序列。对于这类问题，动态数组是首选，例如 C++ 的 std::vector、Java 的 ArrayList 或 Python 的 list。这些数据结构提供了我们所需的所有功能：动态扩容、末尾增删、随机访问、中间插入和排序。

核心思路：

选择数据结构：声明一个动态数组（如 std::vector<int> vec;）来存储序列。
主循环：读取操作总次数 q，然后循环 q 次。
操作分发：在循环内部，读取每行的操作类型码（1到8），然后使用 if-else if 或 switch 结构来执行对应的操作。

各操作的具体实现：

操作 1 (1 x): 调用动态数组的末尾添加方法 (push_back, add, append)。
操作 2 (2): 调用末尾删除方法 (pop_back, remove(size-1), pop)。
操作 3 (3 i): 直接通过下标访问 vec[i]。
操作 4 (4 i x): 调用插入方法，在 i+1 的位置插入 (vec.insert(vec.begin() + i + 1, x))。
操作 5 (5): 调用标准库的升序排序功能 (std::sort, Collections.sort, list.sort())。
操作 6 (6): 调用标准库的降序排序功能。可以直接使用 std::sort 的逆向迭代器或自定义比较器，Java 和 Python 中有更直接的反向排序选项。
操作 7 (7): 获取容器大小 (size(), len())。
操作 8 (8): 遍历数组并打印所有元素。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

void print_vector(const std::vector<int>& vec) {
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << (i == vec.size() - 1 ? "" : " ");
    }
    std::cout << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int q;
    std::cin >> q;
    std::vector<int> vec;
    while (q--) {
        int type;
        std::cin >> type;
        if (type == 1) {
            int x;
            std::cin >> x;
            vec.push_back(x);
        } else if (type == 2) {
            if (!vec.empty()) {
                vec.pop_back();
            }
        } else if (type == 3) {
            int i;
            std::cin >> i;
            std::cout << vec[i] << std::endl;
        } else if (type == 4) {
            int i, x;
            std::cin >> i >> x;
            vec.insert(vec.begin() + i + 1, x);
        } else if (type == 5) {
            std::sort(vec.begin(), vec.end());
        } else if (type == 6) {
            std::sort(vec.rbegin(), vec.rend());
        } else if (type == 7) {
            std::cout << vec.size() << std::endl;
        } else if (type == 8) {
            print_vector(vec);
        }
    }
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine());
        List<Integer> list = new ArrayList<>();
        StringTokenizer st;
        
        while (q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
            
            switch (type) {
                case 1:
                    int x = Integer.parseInt(st.nextToken());
                    list.add(x);
                    break;
                case 2:
                    if (!list.isEmpty()) {
                        list.remove(list.size() - 1);
                    }
                    break;
                case 3:
                    int i3 = Integer.parseInt(st.nextToken());
                    System.out.println(list.get(i3));
                    break;
                case 4:
                    int i4 = Integer.parseInt(st.nextToken());
                    int x4 = Integer.parseInt(st.nextToken());
                    list.add(i4 + 1, x4);
                    break;
                case 5:
                    Collections.sort(list);
                    break;
                case 6:
                    list.sort(Collections.reverseOrder());
                    break;
                case 7:
                    System.out.println(list.size());
                    break;
                case 8:
                    StringBuilder sb = new StringBuilder();
                    for (int j = 0; j < list.size(); j++) {
                        sb.append(list.get(j));
                        if (j < list.size() - 1) {
                            sb.append(" ");
                        }
                    }
                    System.out.println(sb.toString());
                    break;
            }
        }
    }
}

import sys

def main():
    q = int(sys.stdin.readline())
    arr = []
    for _ in range(q):
        line = sys.stdin.readline().split()
        op_type = int(line[0])
        
        if op_type == 1:
            x = int(line[1])
            arr.append(x)
        elif op_type == 2:
            if arr:
                arr.pop()
        elif op_type == 3:
            i = int(line[1])
            print(arr[i])
        elif op_type == 4:
            i = int(line[1])
            x = int(line[2])
            arr.insert(i + 1, x)
        elif op_type == 5:
            arr.sort()
        elif op_type == 6:
            arr.sort(reverse=True)
        elif op_type == 7:
            print(len(arr))
        elif op_type == 8:
            print(*arr)

if __name__ == "__main__":
    main()

算法及复杂度

算法: 基于动态数组的数据结构模拟。
时间复杂度: 设 $Q$ 是操作总数， $N$ 是序列可能达到的最大长度。
- 操作 1, 2, 7 (添加/删除末尾, 获取长度) 是 $\mathcal{O}(1)$ (摊销)。
- 操作 3 (按下标访问) 是 $\mathcal{O}(1)$ 。
- 操作 4 (插入) 是 $\mathcal{O}(N)$ ，因为它可能需要移动后续所有元素。
- 操作 8 (打印) 是 $\mathcal{O}(N)$ 。
- 操作 5, 6 (排序) 是 $\mathcal{O}(N \log N)$ 。
- 总的时间复杂度由所有操作中开销最大的部分决定，如果排序和插入操作频繁，则整体复杂度较高。
空间复杂度: $\mathcal{O}(N)$ ，用于存储序列中的元素。