搜狗笔试题

 一个长度为n的数组a[0],a[1],...,a[n-1]。现在更新数组的名个元素，即a[0]变为a[1]到a[n-1]的积
a[1]变为a[0]和a[2]到a[n-1]的积，...，a[n-1]为a[0]到a[n-2]的积。
程序要求：
要求具有线性复杂度。
不能使用除法运算符。

算法思想：可以申请一个临时数组，然后从右向左进行迭代，然后将相应元素的乘积存储到临时数组的相应位置。

                    然后，从左向右遍历，使用一个临时变量存放相应元素的乘积。

http://topic.csdn.net/u/20110926/09/3756c1fb-8264-481f-8b65-dbaf0d3e4774.html?seed=1907375911&r=75739065#r_75739065

#include "stdafx.h"
#include <iostream>

using namespace std;


void ChangeArray(int arr[], int len)
{
	//临时数组存放从右向左的乘积
	int *temp = new int[len];
	temp[len - 1] = arr[len - 1];
	for (int i = len - 2; i >= 0; --i)
	{
		temp[i] = arr[i] * temp[i+1];
	}

	//临时变量存放从左向右的乘积
	int left = arr[0];
	arr[0] = temp[1];

	//进行计算
	int cur = 0;
	for (int i = 1; i < len - 1; i++)
	{
		cur = arr[i];
		arr[i] = left * temp[i+1];
		left = left * cur;
	}
	arr[len -1] = left;
}
int main()
{
	int arr[] = {1, 2, 3, 4, 5, 6};
	int len = sizeof(arr) / sizeof(int);

	ChangeArray(arr, len);

	for (int i = 0; i < len; ++i)
		cout<<arr[i]<<" ";
	cout<<endl;
}