### Hadoop2面试题解析——腾讯2012年实习生招聘笔试题
#### 题目背景
在2012年的腾讯实习生招聘过程中，出现了一道关于数组处理的编程题，该题目不仅考验应聘者的算法基础，还对其数据结构理解和编程能力提出了较高要求。
#### 题目描述
给定一个长度为`n`的数组`a[n]`，要求构造一个新的数组`b[n]`，使得对于每一个`i` (0 ≤ i < n)，`b[i]`等于`a[0] * a[1] * … * a[n-1] / a[i]`，但题目明确规定不能使用除法操作。此外，还需满足以下条件：
- 时间复杂度为O(n)
- 空间复杂度为O(1)
- 除了迭代器`i`外，不允许使用任何其他变量（包括栈临时变量等）
#### 分析与解答
此题的关键在于如何在不使用除法的情况下计算出目标结果，同时满足时间和空间复杂度的要求。下面将详细介绍两种解法，并分析其优缺点。
### 解法一：两遍扫描法
**思路概述：**
1. **前向扫描**：从左到右计算每个元素左侧所有元素的乘积，存储到新数组`b[]`中。
2. **后向扫描**：从右到左计算每个元素右侧所有元素的乘积，累乘到`b[]`中的相应位置上。
**具体步骤：**
1. 初始化`b[0] = 1`，因为`b[0]`不需要考虑左侧元素的乘积。
2. 使用一个循环从`i = 1`到`N-1`，计算`b[i] = b[i-1] * a[i-1]`，这样`b[i]`就包含了数组`a`中前`i`个元素的乘积。
3. 再次使用一个循环从`i = N-2`到`0`，更新`a[i]`使其等于`a[i+1] * a[i]`，这里利用了`a`数组来暂存右侧元素的乘积。
4. 最后再次遍历数组`b`，更新`b[i] = b[i] * a[i+1]`，完成整个计算过程。
**代码实现：**
```c
#include<stdio.h>
#include<stdlib.h>
#define N 10
int main() {
int a[N], b[N], i;
for (i = 0; i < N; i++) {
a[i] = i + 1;
}
b[0] = 1;
for (i = 1; i < N; i++) {
b[i] = b[i-1] * a[i-1];
}
for (i = N-2; i > 0; i--) {
a[i] = a[i+1] * a[i];
}
for (i = 0; i < N-1; i++) {
b[i] = b[i] * a[i+1];
printf("%d ", b[i]);
}
printf("\n");
return 0;
}
```
**优点：**
- 达到了题目要求的时间和空间复杂度。
- 思路简单清晰，易于理解。
**缺点：**
- 修改了原数组`a`，可能会导致后续使用出现问题。
### 解法二：优化版本
为了克服解法一中对原数组`a`的修改问题，可以采用如下方法：
**思路概述：**
1. **初始化**：`b[0] = 1`。
2. **前向扫描**：计算左侧元素的乘积并存储到`b`中。
3. **后向扫描**：通过更新`b[0]`来计算右侧元素的乘积，然后依次计算`b[i]`。
**代码实现：**
```c
#include<stdio.h>
#include<stdlib.h>
#define N 10
int main() {
int a[N], b[N], i;
for (i = 0; i < N; i++) {
a[i] = i + 4;
}
b[0] = 1;
for (i = 1; i < N; i++) {
b[i] = b[i-1] * a[i-1];
}
for (i = N-2; i > 0; i--) {
b[0] *= a[i+1];
b[i] *= b[0];
}
b[0] *= a[1];
for (i = 0; i < N; i++) {
printf("%d ", b[i]);
}
return 0;
}
```
**优点：**
- 不再修改原数组`a`。
- 依然满足时间复杂度O(n)和空间复杂度O(1)的要求。
**总结：**
这两种解法都很好地解决了原问题，但在实际应用中，更倾向于选择第二种解法，因为它既保持了原数组不变，又实现了高效计算。此类题目不仅考察了应聘者的基础算法能力，也对其编码细节处理能力进行了考察，是Hadoop等大数据领域面试中常见的题目类型之一。
