当前位置:首页 » 编程语言

leetcode_Product of Array Except Self

2015-08-12 09:21 本站整理 浏览(137)

描述:

Given an array of n integers where n > 1,

nums
,return an array
output
such that
output[i]
is

equal to the product of all the elements of

nums
except
nums[i]
.Solve it without division and in O(n).

For example, given

[1,2,3,4]
, return
[24,12,8,6]
.Follow up:

Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

思路:

1.该题目的要求返回一个数组,该数组的product[i]=num[0]*num[1]*.....num[i-1]*num[i+1]*...*num[num.length-1];

2.由于要求出除i位置的元素num[i]的其它所有元素的乘积,假如每次都这么循环遍历一次并作乘法运算,当到num[i]的时候跳过,这样时间复杂度就是O(n*n)

3.另外一种思路就是求出所有的元素的乘积productTotal,然后具体求某个product[i]时,直接product[i]=productTotal/num[i]

4.但3中的思路有一个问题,就是productTotal有可能溢出,为处理这种情况,将productTotal初始化为long类型,OK!

代码:

public int[] productExceptSelf(int[] nums)
	{
		if (nums == null || nums.length == 0)
			return nums;
		long result = 1;
		for (int num : nums)
			result *= num;
		if(result!=0)
		{
			for (int i = 0; i < nums.length; i++)
				nums[i] = (int) (result / nums[i]);
		}else 
		{
			int newArr[]=new int[nums.length];
			newArr=Arrays.copyOf(nums, nums.length);
			for (int i = 0; i < nums.length; i++)
			{
				if(newArr[i]!=0)
					nums[i]=0;
				else 
				{
					int tempProduct=1;
					for(int j=0;j<nums.length;j++)
					{
						if(j==i)
							continue;
						else 
							tempProduct*=newArr[j];
						
					}
					nums[i]=tempProduct;
				}
			}
		}
		return nums;
	}