一维数组编程实战：三道经典算法题解析

1. 从零掌握一维数组：三道经典编程题深度解析

作为一名从学生时代就开始刷题的"老码农"，我深知数组作为编程基础的重要性。今天想和大家分享三道特别适合巩固一维数组知识的经典题目——它们来自我当年备战编程竞赛时的练习题库，看似简单却暗藏玄机。这些题目不仅能帮你理解数组的基本操作，更能培养解决实际问题的思维模式。

这三道题分别是：修理牛棚（基础题49th）、按要求输出序列（基础题50th）和部落人乘法（基础题51th）。它们都只需要使用一维数组就能解决，但每道题考察的侧重点各不相同。接下来我会带大家逐题分析，从问题理解到解法实现，再到优化思路，最后分享一些只有踩过坑才知道的注意事项。

2. 修理牛棚（基础题49th）——数组遍历与贪心算法实战

2.1 问题描述与理解

想象你是一个农场主，牛棚的木板有些已经损坏。给定一个表示牛棚位置的数组（比如[3,5,8,10]表示第3、5、8、10号位置的木板坏了），以及你拥有的木板数量M（长度不限）。要求用最多M块木板修补所有损坏的位置，如何选择修补方案才能使使用的木板总长度最短？

这个问题看似简单，但有几个关键点需要注意：

1. 木板可以覆盖连续的位置（比如一块长度为3的木板可以覆盖位置5,6,7）
2. 目标是总长度最短，而不是木板数量最少
3. 输入数组可能无序，需要先排序

2.2 解题思路与算法选择

这个问题非常适合使用贪心算法（Greedy Algorithm）来解决。具体步骤如下：

1. 首先对损坏的位置数组进行排序
2. 计算相邻损坏位置之间的距离
3. 对这些距离排序，选择最大的M-1个间隔不覆盖（即在这些间隔处断开木板）
4. 总长度就是最后一个损坏位置 - 第一个损坏位置 + 1 - 这些不覆盖的间隔总和

为什么这样能得到最优解？因为每次选择最大的间隔不覆盖，相当于"节省"了最多的长度。这是贪心算法的典型应用——局部最优导致全局最优。

2.3 C++代码实现与逐行解析

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int M, S, C; cin >> M >> S >> C; vector<int> stalls(C); for (int i = 0; i < C; ++i) { cin >> stalls[i]; } if (M >= C) { cout << C << endl; return 0; } sort(stalls.begin(), stalls.end()); vector<int> gaps; for (int i = 1; i < C; ++i) { gaps.push_back(stalls[i] - stalls[i-1] - 1); } sort(gaps.begin(), gaps.end(), greater<int>()); int total = stalls.back() - stalls.front() + 1; for (int i = 0; i < M - 1 && i < gaps.size(); ++i) { total -= gaps[i]; } cout << total << endl; return 0; }

代码解析：

1. 首先输入木板数量M，牛棚总长度S（实际未使用），损坏位置数C
2. 读取所有损坏位置存入数组stalls
3. 特殊情况处理：如果木板数量≥损坏位置数，每个损坏位置用一块木板，总长度就是C
4. 对损坏位置排序
5. 计算相邻位置间的间隔（gap）
6. 对间隔从大到小排序
7. 初始总长度是第一个到最后一个损坏位置的距离
8. 减去最大的M-1个间隔（相当于在这些地方断开木板）
9. 输出最终总长度

2.4 常见错误与调试技巧

新手在解决这个问题时容易犯的几个错误：

1. 未考虑排序：直接计算间隔会导致错误，必须先排序
2. 边界条件处理不足：当M≥C时应该直接返回C
3. 间隔计算错误：两个相邻位置a和b的间隔应该是b-a-1，而不是简单的b-a
4. 数组越界：当M=1时，M-1=0，循环可能不执行，需要正确处理

调试技巧：

• 打印中间变量（排序后的数组、间隔数组等）
• 测试边界情况：M=1，M=C，所有损坏位置连续等情况
• 使用小规模数据手动验证

3. 按要求输出序列（基础题50th）——数组操作与双指针技巧

3.1 问题重述与示例分析

给定一个整数数组，要求重新排列数组元素，使得所有奇数位于数组前半部分，所有偶数位于后半部分，并保持奇数之间、偶数之间的相对顺序不变。

例如： 输入：[1,2,3,4,5] 输出：[1,3,5,2,4]

这个问题考察的是如何在保持元素相对顺序的前提下，对数组进行特定条件的重新排列。看似简单，但如果要求时间复杂度O(n)，空间复杂度O(1)，就变得很有挑战性了。

3.2 双指针解法详解

这个问题可以使用双指针技巧高效解决：

1. 使用一个"写指针"表示当前应该写入的位置
2. 遍历数组，遇到奇数就放到写指针位置，然后写指针前进
3. 第一遍结束后，所有奇数都在前面且顺序正确
4. 同样方法处理偶数

但这种方法需要两次遍历。更优的方法是使用类似归并排序中的"稳定划分"思想：

void reorderArray(vector<int>& nums) { int n = nums.size(); vector<int> res(n); int odd_pos = 0, even_pos = 0; // 计算奇数个数，确定偶数开始位置 for (int num : nums) { if (num % 2 == 1) even_pos++; } for (int num : nums) { if (num % 2 == 1) { res[odd_pos++] = num; } else { res[even_pos++] = num; } } nums = res; }

3.3 时间复杂度与空间复杂度分析

上述解法：

• 时间复杂度：O(n)，两次完整遍历
• 空间复杂度：O(n)，需要额外数组

如果要求原地排序（O(1)空间），可以使用类似插入排序的方法，但时间复杂度会退化到O(n²)。在面试中，通常O(n)空间的解法已经足够。

3.4 变种问题与扩展思考

这个问题有几个有趣的变种：

1. 不保持相对顺序：可以使用快速排序的分区思想，双指针从两端向中间移动
2. 多条件排序：比如正负数分离，能被3整除的数在前等
3. 多指针技巧：如果需要分成三部分或更多，可以扩展多指针方法

思考：如果要求同时满足多个条件（如奇数在前且升序排列），应该如何修改算法？

4. 部落人乘法（基础题51th）——数组模拟与高精度计算

4.1 问题背景与数学原理

部落人乘法是一种古老的乘法计算方法，类似于我们小学学习的竖式乘法，但采用了一种特殊的进位方式。题目要求模拟这种乘法过程，通常涉及大数运算（超出普通整数范围）。

具体规则：

1. 将两个数字的每一位相乘，不考虑进位
2. 将相同位数的结果相加
3. 最后处理进位

例如：计算123 × 45

1 2 3 × 4 5 ---------- 5 10 15 4 8 12 ---------- 4 13 22 15 然后处理进位：5 5 5 3 5 → 5535

4.2 数组模拟实现步骤

用数组模拟这个过程的关键步骤：

1. 将两个数字转换为数组（或字符串），逆序存储（方便计算）
2. 创建结果数组，长度为两个数字长度之和
3. 双重循环，计算每一位的乘积并累加到结果数组对应位置
4. 处理进位
5. 去除前导零，逆序输出结果

4.3 C++代码实现与注释

#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; string multiply(string num1, string num2) { if (num1 == "0" || num2 == "0") return "0"; int m = num1.size(), n = num2.size(); vector<int> res(m + n, 0); reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int digit1 = num1[i] - '0'; int digit2 = num2[j] - '0'; res[i + j] += digit1 * digit2; } } for (int i = 0; i < m + n - 1; ++i) { res[i + 1] += res[i] / 10; res[i] %= 10; } string result; for (int num : res) { result += to_string(num); } reverse(result.begin(), result.end()); // 去除前导零 size_t start = result.find_first_not_of('0'); if (start != string::npos) { return result.substr(start); } return "0"; } int main() { string a, b; cin >> a >> b; cout << multiply(a, b) << endl; return 0; }

4.4 性能优化与边界情况

优化思路：

1. 减少乘法次数：使用Karatsuba算法可以将时间复杂度降到O(n^1.585)
2. 内存优化：可以边计算边处理进位，减少中间结果存储
3. 并行计算：对于超大数，可以分块并行计算

边界情况处理：

• 乘数为0的情况直接返回"0"
• 前导零的处理
• 数字非常大的情况（可能需要分段计算）

5. 一维数组编程的通用技巧与心得

经过这三道题的练习，我总结了一些关于一维数组编程的通用技巧：

1. 排序是利器：很多数组问题在排序后会变得简单（如修理牛棚问题）
2. 双指针技巧：适用于需要同时跟踪多个位置的问题（如按要求输出序列）
3. 逆序存储：对于数字计算类问题，逆序存储可以简化索引计算
4. 画图辅助：在纸上画出数组和指针的变化过程，能帮助理清思路
5. 边界测试：特别注意空数组、单元素数组、全相同元素等特殊情况

在实际编程竞赛或面试中，数组问题往往看起来简单，但要写出高效、健壮的代码并不容易。我的建议是：

• 先确保基本解法正确，再考虑优化
• 多使用assert或打印中间结果验证程序状态
• 对于复杂的索引计算，可以封装成辅助函数提高可读性
• 多练习各种类型的数组问题，培养直觉

最后分享一个我常用来生成测试用例的小技巧：对于数组问题，可以写一个随机数组生成器，包含各种边界情况，然后用简单但正确的方法（如暴力法）作为验证。