题目:给定一数组a[N]，我们希望构造数组b [N]，其中b[j]=a[0]*a[1]…a[N-1] / a[j]，在构造过程中，不允许使用除法：要求O（1）空间复杂度和O（n）的时间复杂度；除遍历计数器与a[N] b[N]外，不可使用新的变量（包括栈临时变量、堆空间和全局静态变量等）；实现程序（主流编程语言任选）实现并简单描述。(注意黑体)
中间变量解法:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
NSArray
*firstArr=[[
NSArray
alloc]initWithObjects:@
"3"
,@
"5"
,@
"8"
,@
"10"
,
nil
];
NSMutableArray
*secondArr=[[
NSMutableArray
alloc]init];
[secondArr addObject:[
NSNumber
numberWithInteger:1]];
for
(
NSInteger
i=1; i<[firstArr count]; i++) {
[secondArr addObject:[
NSNumber
numberWithInteger:[secondArr[i-1] integerValue]*[firstArr[i-1] integerValue]]];
}
NSInteger
temp=1;
for
(
NSInteger
i=[firstArr count]-2; i>=0; i--) {
temp *=[firstArr[i+1] integerValue];
secondArr[i]=[
NSNumber
numberWithInteger:temp*[secondArr[i] integerValue]];
}
for
(
NSInteger
i=0; i<[secondArr count]; i++) {
NSLog
(@
"中间变量交换:%@"
,secondArr[i]);
}
NSLog
(@
"iOS技术交流群:228407086"
);
NSLog
(@
"原文地址:http://www.cnblogs.com/xiaofeixiang"
);
|
效果如下:
第一个循环不是特别好想，循环具体过程是这样的:
secondArr[0] ->1
secondArr[1] ->firstArr[0]*secondArr[0] =firstArr[0]
secondArr[2] ->firstArr[1]*secondArr[1] =firstArr[1]*firstArr[0]
secondArr[3] ->firstArr[2]*secondArr[2] =firstArr[2]*firstArr[1]*firstArr[0]
最后我们想要得到的结果，应该是这样的:
secondArr[0] ->firstArr[1]*firstArr[2]*firstArr[3]
secondArr[1] ->firstArr[0]*firstArr[2]*firstArr[3]
secondArr[2] ->firstArr[0]*firstArr[1]*firstArr[3]
secondArr[3] ->firstArr[0]*firstArr[1]*firstArr[2]
因此我们只需要重新遍历依稀，从后向前将对应的索引位置乘以缺失的变量即可,第二个循环就是解决这个问题的，可以得到最后的结果，不过题目中不需要使用中间变量，我们可以使用secondArr[0]作为中间变量，修改如下:
|
1
2
3
4
5
6
7
8
9
|
secondArr[0]=[
NSNumber
numberWithInteger:1];
for
(
NSInteger
i=[firstArr count]-1; i>=1; i--) {
secondArr[i]=[
NSNumber
numberWithInteger:[secondArr[0] integerValue]*[secondArr[i] integerValue]];
secondArr[0]=[
NSNumber
numberWithInteger:[secondArr[0] integerValue]*[firstArr[i] integerValue]];
}
for
(
NSInteger
i=0; i<[secondArr count]; i++) {
NSLog
(@
"当前的值:%@"
,secondArr[i]);
}
|
结果也是一样的:
这个题目最主要的是从前向后和从后向前遍历，类似于快速排序的切分的意思~
