刷题笔记合集🔗

数组拼接

问题描述

现在有多组整数数组，需要将它们合并成一个新的数组。合并规则如下：从每个数组里按顺序取出固定长度的内容合并到新的数组中，取完的内容会删除掉。如果该行不足固定长度或者已经为空，则直接取出剩余部分的内容放到新的数组中，继续下一行。

输入格式

第一行是每次读取的固定长度 ，满足 。

第二行是整数数组的数目 ，满足 。

第 到第 行是需要合并的数组，不同的数组用回车换行分隔，数组内部用逗号分隔，每个数组最多不超过 个元素。

输出格式

输出一个新的数组，用逗号分隔。

样例输入1

3
2
2,5,6,7,9,5,7
1,7,4,3,4

样例输出1

2,5,6,1,7,4,7,9,5,3,4,7

样例输入2

4
3
1,2,3,4,5,6
1,2,3
1,2,3,4

样例输出2

1,2,3,4,1,2,3,1,2,3,4,5,6

样例输入3

3
2
2,5,6,7,,,9,5,7
1,7,4,3,,4

样例输出3

2,5,6,1,7,4,7,9,5,3,4,7

样例解释

数据范围

• 
• 
• 每个数组最多不超过 个元素

题解

这道题目的核心是要理解如何按照给定的规则合并多个数组。我们可以用一个简单的循环来实现这个过程。

首先，我们需要读取固定长度 和数组数目 。然后，我们可以使用一个列表来存储所有的输入数组。

合并过程可以这样进行：

1. 创建一个空的结果列表。
2. 循环遍历所有输入数组，每次从当前数组取出 个元素（或者如果数组长度不足 ，就取出所有剩余元素）。
3. 将取出的元素添加到结果列表中。
4. 如果当前数组还有剩余元素，就将其放回数组列表的末尾。
5. 重复步骤2-4，直到所有数组都被处理完毕。

这个算法的时间复杂度是 ，其中 是所有数组中元素的总数。因为我们只需要遍历每个元素一次。

空间复杂度也是 ，因为我们需要存储所有的输入元素和输出结果。

对于给定的数据范围（，每个数组最多100个元素），这个算法是完全可以接受的。即使在最坏情况下（1000个数组，每个数组100个元素），总元素数也只有100000，现代计算机可以在很短的时间内处理这么多元素。

需要注意的是，输入可能包含空元素，我们需要在读取输入时过滤掉这些空元素。这可以通过使用filter函数或列表推导式来实现。

参考代码

• Python

# 读取固定长度L
L = int(input())
# 读取数组数目N
N = int(input())

# 读取并处理输入数组，过滤掉空元素
arrays = [list(filter(lambda x: x != "", input().split(","))) for _ in range(N)]

# 初始化结果列表
result = []

# 当还有数组未处理完时，继续循环
while arrays:
    # 取出第一个数组
    current_array = arrays.pop(0)
    
    # 如果当前数组长度大于等于L，取前L个元素
    if len(current_array) >= L:
        result.extend(current_array[:L])
        # 如果数组还有剩余元素，将剩余部分放回数组列表末尾
        if len(current_array) > L:
            arrays.append(current_array[L:])
    else:
        # 如果当前数组长度小于L，取所有元素
        result.extend(current_array)

# 将结果转换为字符串并打印
print(",".join(result))

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_ARRAYS 1000
#define MAX_ELEMENTS 100

// 函数用于分割字符串
int split(char* str, char* delim, char** result) {
    int count = 0;
    char* token = strtok(str, delim);
    while (token != NULL) {
        if (strlen(token) > 0) {
            result[count++] = token;
        }
        token = strtok(NULL, delim);
    }
    return count;
}

int main() {
    int L, N;
    char line[1000];
    char* arrays[MAX_ARRAYS][MAX_ELEMENTS];
    int array_lengths[MAX_ARRAYS] = {0};
    char* result[MAX_ARRAYS * MAX_ELEMENTS];
    int result_count = 0;

    // 读取固定长度L
    scanf("%d", &L);
    // 读取数组数目N
    scanf("%d", &N);
    getchar(); // 消耗换行符

    // 读取并处理输入数组
    for (int i = 0; i < N; i++) {
        fgets(line, sizeof(line), stdin);
        line[strcspn(line, "\n")] = 0; // 移除换行符
        array_lengths[i] = split(line, ",", arrays[i]);
    }

    int current_array = 0;
    while (1) {
        int elements_to_take = L;
        if (array_lengths[current_array] < L) {
            elements_to_take = array_lengths[current_array];
        }

        // 取出元素并添加到结果中
        for (int i = 0; i < elements_to_take; i++) {
            result[result_count++] = arrays[current_array][i];
        }

        // 更新数组
        for (int i = elements_to_take; i < array_lengths[current_array]; i++) {
            arrays[current_array][i - elements_to_take] = arrays[current