首页 > 代码库 > leetcode_Product of Array Except Self

leetcode_Product of Array Except Self

描写叙述:

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 ofnums 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;
	}


leetcode_Product of Array Except Self