【转】白话算法经典系列之十四
问题描述:现有一数组a[N-1],求另外一数组b[N-1]
问题约束:1.不能用除法 2.不能用除了遍历a,b两数组需要的变量之外的变量 3.时间复杂度为O(N),空间复杂度为O(1)
解法:
// 腾讯2012年实习生笔试加分题 //http://blog.csdn.net/morewindows/article/details/8742666 //By MoreWindows( http://blog.csdn.net/MoreWindows ) #include <stdio.h> void PrintfArray(int a[], int n) { for (int i = 0; i < n; i++) printf("%5d ", a[i]); putchar('\n'); } int main() { printf(" 腾讯2012年实习生笔试加分题 \n"); printf(" - http://blog.csdn.net/morewindows/article/details/8742666 -\n"); printf(" -- By MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n"); const int MAXN = 5; int a[MAXN] = {1, 3, 5, 7, 9}; int b[MAXN]; printf("数组a为:\n"); PrintfArray(a, MAXN); b[0] = 1; int i; for (i = 1; i < MAXN; i++) b[i] = b[i - 1] * a[i - 1]; int b[0] = 1; for (i = MAXN - 2; i >= 1; i--) { b[0]*= a[i + 1]; b[i] *= b[0]; } printf("数组b为:\n"); PrintfArray(b, MAXN); return 0; }