现在的位置: 首页 > 综合 > 正文

求数组中除第i个外的所有其他数组元素的乘积

2019年09月23日 ⁄ 综合 ⁄ 共 2732字 ⁄ 字号小中大 ⁄ 评论关闭

一、问题描述

输入一个数组source_numbers，现在求一个target_numbers，target_numbers满足下面的关系式：

要求：不能够使用除法。

举个例子，比如source_numbers＝{1, 2, 3, 4, 5};则求出的target_numbers ＝ {120, 60, 40, 30, 24}。

这是Google曾经的一道面试题，今年腾讯的实习笔试也出了这道题。

二、问题分析

问题中有一个要求，就是不允许使用除法。很自然的就想到只要按照上述的那个关系式做乘积即可。

下面是第一种方法。用两层循环来表示，外层循环从0到数组的长度减1(n - 1)。内层有两个循环一个是从数组的第0个元素乘到第i - 1个元素，另一个循环是从数组的最后一个元素n-1乘i + 1。

这里不给出伪代码了，后面程序有实现。这种方法的时间复杂度是。

下面重点给出第二种方法。我们把发杂度降到O(n)。要想降低时间复杂度，就要拿空间还换。根据第一种方法的思路，内层有两个循环，一个是从第一个元素乘到第i - 1个元素，一个是从最后一个元素乘到第i + 1。那么我们可以用两个数组来保存两个乘积，保存的形式可以自己设计。这个思路也是比较简单的，但是把时间的复杂程度降到了O(3n)。

我下面给出的程序的思路是用prefix_numbers来保存从前乘到后面的结果，即prefix_numbers[i]＝ source_numbers[0]*...*source_numbers[i - 1]，其中i>0。我们注意到prefix_numbers并不需要保存原数组中的所有元素，所以我们可以把prefix_numbers[0]赋值为1。同样的思路可以求得suffix_numbers[i]
= source_numbers[i - 1]*...*source_numbers[n - i]，其中i>0，同样的把suffix_number[0]赋值为1。那么所求的数组元素有关系式target_numbers[i] = prefix_numbers[i] * suffix_numbers[n - i - 1]；

另外，还需要一点就是乘积的结果可能较大(在基本数据类型能表示的范围内)，所以除source_numbers数组时int型外，其他的都用long型。

三、程序实现

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char const *argv[])
{
	int n,
		i;
	int* source_numbers = NULL;
	long* target_numbers = NULL;
	long* prefix_numbers = NULL;
	long* suffix_numbers = NULL;

	printf("Please input a integer number n(n > 1): \n");

	while(EOF != (scanf("%d", &n)))
	{
		source_numbers = (int*)malloc(n * sizeof(int));
		target_numbers = (long*)malloc(n * sizeof(long));
		prefix_numbers = (long*)malloc(n * sizeof(long));
		suffix_numbers = (long*)malloc(n * sizeof(long));

		void print_result(long*, int);

		printf("Please enter %d integers\n", n);

		i = 0;
		while(i++ < n)
			scanf("%d", &source_numbers[i - 1]);

		/*
		*the first method
		*/
		int j,
			k;
		for(i = 0; i < n; i++)
		{
			target_numbers[i] = 1;
			for(j = 0; j < i; j++)
				target_numbers[i] *= source_numbers[j];
			for(k = n - 1; k > i; k--)
				target_numbers[i] *= source_numbers[k];
		}

		printf("the result of first method:\n");
		print_result(target_numbers, n);

		//reset the target_numbers
		free(target_numbers);
		target_numbers = (long*)malloc(n * sizeof(long));

		/*
		* the second method
		*/
		prefix_numbers[0] = 1;
		for(i = 1; i < n; i++)
			prefix_numbers[i] = prefix_numbers[i - 1] * source_numbers[i - 1];

		suffix_numbers[0] = 1;
		for(i = 1; i < n; i++)
			suffix_numbers[i] = suffix_numbers[i - 1] * source_numbers[n - i]; 

		for(i = 0; i < n; i++)
			target_numbers[i] = prefix_numbers[i] * suffix_numbers[n - i - 1];

		printf("the result of second method:\n");
		print_result(target_numbers, n);

		free(source_numbers);
		free(target_numbers);
		free(prefix_numbers);
		free(suffix_numbers);

		printf("Please input a integer number n(n > 1): \n");
	}

	return 0;
}
void print_result(long* target_numbers, int n)
{
	int i;

	printf("%ld...", target_numbers[0]);
	for(i = 1; i < n - 1; i++)
		printf("%ld...", target_numbers[i]);
	printf("%ld\n", target_numbers[n - 1]);
	printf("\n");
}