O(n) time and O(1) space C++ solution with explanation


  • 103
    Z

    First, consider O(n) time and O(n) space solution.

    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            int n=nums.size();
            vector<int> fromBegin(n);
            fromBegin[0]=1;
            vector<int> fromLast(n);
            fromLast[0]=1;
            
            for(int i=1;i<n;i++){
                fromBegin[i]=fromBegin[i-1]*nums[i-1];
                fromLast[i]=fromLast[i-1]*nums[n-i];
            }
            
            vector<int> res(n);
            for(int i=0;i<n;i++){
                res[i]=fromBegin[i]*fromLast[n-1-i];
            }
            return res;
        }
    };
    

    We just need to change the two vectors to two integers and note that we should do multiplying operations for two related elements of the results vector in each loop.

    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            int n=nums.size();
            int fromBegin=1;
            int fromLast=1;
            vector<int> res(n,1);
            
            for(int i=0;i<n;i++){
                res[i]*=fromBegin;
                fromBegin*=nums[i];
                res[n-1-i]*=fromLast;
                fromLast*=nums[n-1-i];
            }
            return res;
        }
    };

  • 3
    S

    OK, if doesn't count the space of the return array, it is O(1) space.


  • 0
    L

    It's easy to understand, but really hard for me to come up on my own! Amazing!


  • 0
    T

    Java version:

    class Solution {
        public int[] productExceptSelf(int[] nums) {
            int[] res = new int[nums.length];
            Arrays.fill(res, 1);
            int fromBegin = 1;
            int fromEnd = 1;
            for (int i = 0; i < nums.length; ++i) {
                res[i] *= fromBegin;
                fromBegin *= nums[i];
                res[nums.length - 1 - i] *= fromEnd;
                fromEnd *= nums[nums.length - 1 - i];
            }
            return res;
        }
    }
    

  • 0
    L

    @ltong2016 是我菜,没理解~_~


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.