LeetCode238. Product of Array Except Self

题意

给一个数组A，生成一个数组B，B[i] = A[0] x A[1] x..x A[i-1] x A[i+1] x..x A[n]
时间复杂度O(N)，不能使用除法

思路

仔细看一下，其实每次计算B[i]就是前面i-1个元素相乘，乘上后面i+1个元素相乘。
所以只要预处理前缀积和后缀积即可。

代码

  1. 版本1 O(N)，S(N)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public class Solution {
        	public int[] productExceptSelf(int[] nums) {
            	int[] pre = new int[nums.length];//前缀积
            	int[] sub = new int[nums.length];//后缀积
            	int[] ans = new int[nums.length];
            	pre[0] = nums[0];
            	sub[nums.length-1]=nums[nums.length-1];
            	for(int i = 1;i<nums.length;i++)
                	pre[i] = pre[i-1]*nums[i];
            	for(int i = nums.length-2;i>=0;i--)
                	sub[i] = sub[i+1]*nums[i];
            	ans[0] = sub[1];
            	ans[nums.length-1]=pre[nums.length-2];
            	for(int i = 1;i<nums.length-1;i++)
                	ans[i] = pre[i-1]*sub[i+1];//前i-1个的积*后i+1个的积
            	return ans;
        	}
    }

  2. 版本2 O(N),S(1)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public class Solution {
    		public int[] productExceptSelf(int[] nums) {
        		int n = nums.length;
        		int[] res = new int[n];
        		res[0] = 1;
        		for (int i = 1; i < n; i++)
            		res[i] = res[i - 1] * nums[i - 1];//res[i]保存的是前i-1个数的积
        		int right = 1;
        		for (int i = n - 1; i >= 0; i--) {
            		res[i] *= right;//当前的right值为后i+1个数的积
            		right *= nums[i];//更新为后i个数的积
        		}
        		return res;
    		}
    }

留言

2017-01-31
⬆︎TOP