Leetcode——238除自身以外數組的乘積

238.除自身以外數組的乘積

給定長度為 n 的整數數組 nums，其中 n > 1，傳回輸出數組 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其餘各元素的乘積。

示例：

輸入：[1,2,3,4]
輸出：[24,12,8,6]
           

說明：請不要使用除法，且在O(n)時間複雜度内完成此題。

【思路】

根據題意，在O(n)時間複雜度内，于是此時想到首先周遊一次數組，把所有數組元素的乘積計算出來。然後再依次周遊做除法，但是問題在于，題上要求不能使用除法。是以按照題上的要求，隻能利用解析中的解法。

首先計算從左到右，除去目前元素的左邊的元素的乘積，然後再計算從右到左除去目前元素的右邊的元素的乘積然後相乘。

【實作代碼】

package leetcode_50;

import java.util.Scanner;


public class Leetcode_238 {

	public static void main(String[] args){
		Scanner scanner=new Scanner(System.in);
		String string=scanner.nextLine();
		String[] strings=string.split(",");
		int[] a=new int[strings.length];
		for(int i=0;i<strings.length;i++){
			a[i]=Integer.parseInt(strings[i]);
		}
		
		productExceptSelf(a);
		scanner.close();
	}

	private static void productExceptSelf(int[] nums) {

		
		//除自身外數組的乘積
		int[] res=new int[nums.length];
		int k=1;
		for(int i=0;i<res.length;i++){
			res[i]=k;
			k=k*nums[i];  //此時數組存儲的是出去目前元素最左邊的元素乘積
		}
		k=1;
		for(int i=res.length-1;i>=0;i--){
			res[i]*=k;    //此時數組等于左邊的*該數右邊的
			k*=nums[i];  // k為該數右邊的乘積
		}
		for(int i=0;i<res.length;i++){
			System.out.print(res[i]);
		}
	}
	
	
}

           

【注意】

在做題的時候首先需要把握題意，并且從多方面考慮題目，都可以使用哪些方式實作，多關注題目的要求和輸出結果來找思路。