在 C++ 中通过重复步骤和模运算转换数组

引言

数组是计算机科学中的基本数据结构，它提供了一种方便的方式来存储和操作元素集合。在某些情况下，我们会遇到需要通过重复步骤并结合特定规则来转换数组的问题。本文探讨了这样一种场景，即给定一个整数数组，我们对每个元素执行一系列涉及模运算和元素加法的步骤。

问题陈述

考虑一个 **大小为 N 的数组 A**。我们的任务是对数组中的每个元素重复一组指定的步骤（T 次）。这些步骤包括将每个元素加一，并应用模 81 的运算。此外，如果在任何时候数组中的某个元素等于 80，则在数组末尾追加一个值为 0 的新元素。目标是确定执行这些转换后数组的大小。

为什么要转换数组？

在编程和数据分析中，转换数组是至关重要的。此过程对于解决问题、数据处理、算法操作、标准化、预处理、模式识别、提高效率、数学运算以及适应特定约束条件至关重要。这些转换有助于简化问题、标准化数据、优化算法和揭示模式，最终为有效的数据分析和高效的算法解决方案做出贡献。

许多算法问题需要转换数组以满足特定条件或约束。转换过程可以简化解决问题的方法。

在数据科学和分析中，可能需要转换数组以方便处理、聚合或提取有意义的信息。

示例

示例 1

N = 4

A = [65, 2, 80, 4]

T = 3

输出 5

说明

步骤 1：初始数组

[65, 2, 80, 4]

步骤 2：第一次迭代

• 将每个元素加 1。
• 将每个元素应用模 81 运算。
• 如果某个元素变为 80，则在末尾添加一个新元素 0。
• 第一次迭代后

[66, 3, 0, 5, 1]

• 由于遇到了元素 80 并追加了新元素，大小增加到 5。

步骤 3：第二次迭代

• 将每个元素加 1。
• 将每个元素应用模 81 运算。
• 如果某个元素变为 80，则在末尾添加一个新元素 0。
• 第二次迭代后

[67, 4, 1, 6, 2]

• 此迭代中没有添加新元素，因此大小保持为 5。

步骤 4：第三次迭代

• 将每个元素加 1。
• 将每个元素应用模 81 运算。
• 如果某个元素变为 80，则在末尾添加一个新元素 0。
• 第三次迭代后

[68, 5, 2, 7, 3]

• 同样，没有添加新元素，大小保持为 5。

示例 2

N = 4

A = {80, 80, 79, 79}

T = 2

步骤 1：初始数组

[80, 80, 79, 79]

步骤 2：第一次迭代

• 将每个元素加 1。
• 将每个元素应用模 81 运算。
• 如果某个元素变为 80，则在末尾添加一个新元素 0。
• 第一次迭代后

[0, 0, 80, 80, 0, 0]

• 在此，由于第一次迭代中有两个元素变成了 80，因此在数组中追加了两个新元素。

步骤 3：第二次迭代

• 将每个元素加 1。
• 将每个元素应用模 81 运算。
• 如果某个元素变为 80，则在末尾添加一个新元素 0。
• 第二次迭代后

[1, 1, 0, 0, 1, 1, 0, 0]

• 在第二次迭代中，数组经历了进一步的转换。两个现有的 80 被替换为 0，并且当某些元素再次达到 80 时会添加新元素。最终数组的大小现在是 8。

经过两次上述转换迭代后，最终数组为 **[1, 1, 0, 0, 1, 1, 0, 0]**，数组大小为 8。该过程包括将每个元素加一，应用模 81 运算，并在元素达到 80 时追加值为 0 的新元素。此示例说明了数组的大小如何根据指定的规则和迭代次数动态增长。

编码

输出

Final Array Size: 8

说明

1. calculateFinalArraySize 函数

• 此函数用于计算在指定步数 **(totalSteps)** 后数组的大小。
• 数组 **frequencyCount** 用于跟踪输入数组中每个元素的频率。
• 开头的循环计算输入数组（elements）中每个元素的初始频率。
• 第二个循环遍历指定的步数 **(totalSteps)**。
• 在此循环内部，它根据问题陈述中描述的规则更新频率。
• 它使用临时变量来交换频率，确保更新准确。
• 对于元素 0，它用前一个元素（本例中为 80）的频率更新其频率。
• 对于元素 1，它将其频率增加元素 0 的频率。
• 它应用模运算以避免整数溢出。
• 第二个循环结束后，它计算 frequencyCount 数组中所有元素的总和，并考虑模运算。

2. main 函数

• main 函数设置输入参数
• **arraySize：**这是输入数组的大小。
• **inputArray：**包含整数的输入数组。
• **totalSteps：**要执行的步数。
• 之后，它使用这些参数调用 **calculateFinalArraySize** 函数并打印结果。

注意：const int modulo = 1e9 + 7; 是一个常量，用于定义模运算以避免整数溢出。

• 数组 **frequencyCount** 用于有效地跟踪每个元素的频率。
• **calculateFinalArraySize** 函数封装了更新频率和计算特定步数后最终数组大小的逻辑。
• 在提供的示例中，main 函数调用 calculateFinalArraySize，输入数组为 [80, 80, 79, 79]，在 2 步后，它输出最终的数组大小，即 8。

时间和空间复杂度

时间复杂度

• **频率计数：**在 **calculateFinalArraySize** 函数中，用于计算每个元素初始频率的循环运行时间为 **O(N)**，其中 N 是输入数组的大小。
• **执行 T 步：**执行 T 步的循环有一个常数上限 81 次迭代，这不取决于输入数组的大小。因此，它对时间复杂度贡献 **O(1)**。
• **总时间复杂度：**整体时间复杂度由初始频率计数决定，使其为 **O(N)**。

空间复杂度

• **频率计数数组：****frequencyCount** 数组用于存储每个元素的频率。它的大小为 82（81 个元素 + 1 个额外用于交换过程中的附加 0）。因此，它对空间复杂度贡献 **O(1)**。
• **输入向量：**elements 向量（表示输入数组）对空间复杂度贡献 **O(N)**，其中 N 是输入数组的大小。
• **其他变量：**其余变量和常量的大小固定，不依赖于输入大小。因此，它们对空间复杂度贡献 **O(1)**。

时间复杂度：O(N)

空间复杂度：O(N)

结论

总之，C++ 实现有效地解决了具有重复步骤和模运算的数组转换问题。该算法采用频率计数数组来跟踪元素出现次数，确保时间复杂度为 **O(N)**，空间复杂度为 **O(N)**，其中 N 是数组大小。该代码具有清晰性、可读性以及处理动态数组转换的平衡方法，使其适用于中等大小数组的实际应用。