1 डी अ‍ॅरे लीटकोड सोल्यूशनचा योग चालू आहे


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन सफरचंद ब्लूमबर्ग उबेर
अरे

समस्या विधान

चालू रकमेमध्ये 1 डी अॅरे समस्या आम्हाला एक अ‍ॅरे क्रमांक देण्यात आला आहे ज्यासाठी आम्हाला अ‍ॅरे परत करावी लागेल जिथे निकालाच्या अ‍ॅर मधील प्रत्येक निर्देशांकासाठी मी [i] = बेरीज (संख्या [0]… संख्या [i]).

उदाहरण

 nums = [1,2,3,4]
[1,3,6,10]

स्पष्टीकरण:

चालू रक्कम आहे: [१, १ + २, १ + २ +,, १ + २ + + +]] = [१,,,,, १०]

nums = [1,1,1,1,1]
[1,2,3,4,5]

स्पष्टीकरण:

चालू रक्कम आहे: [१, १ + १, १ + १ + १, १ + १ + १ + १, १ + १ + १ + १ + १] = [१, २,,,,,]]

दृष्टीकोन

या समस्येमध्ये आपल्याला एक अ‍ॅरे तयार करावी लागेल जिथे निर्देशांकातील घटकाचे मूल्य 1 पासून ते ith अनुक्रमित घटकापर्यंत दिलेल्या अ‍ॅरे मधील घटकांच्या बेरीज होईल.
यासाठी आपण दिलेल्या अ‍ॅरे साईझच्या समान आकाराचा अ‍ॅरे बनवू शकतो. नंतर for for लूपमधील प्रत्येक घटकासाठी आपण लूपसाठी दुसरा वापरून इंडेक्स 0 ते इंडेक्स i मध्ये मूळ अ‍ॅरे मध्ये घटक जोडू शकतो. या अल्गोरिदमची वेळ जटिलता ओ (एन ^ 2) असेल.

आम्ही एकच समस्या वापरुन या समस्येची वेळ गुंतागुंत कमी करू शकतो लूप.
क्रमांक दिलेला अ‍ॅरे असू द्या आणि रेस अ‍ॅरे बनू ज्यामध्ये आपण चालू बेरीज संचयित करत आहोत, तर मग रेस [i] खालीलप्रमाणे मोजू शकतो.

रेस [i] = रेस [आय -१] + क्रमांक [i].

उदाहरणः क्रमांक = [1,2,3,4] खाली दिलेल्या आकृतीत दर्शविले आहे,

1 डी अ‍ॅरे लीटकोड सोल्यूशनचा योग चालू आहे

म्हणून प्रत्यय पुन्हा काढण्यासाठी लूप चालवण्याची गरज नाही कारण आधीच्या रेस अ‍ॅरेच्या आधीच्या अनुक्रमणिकेमध्ये मी अनुक्रमणिका संचयित करेपर्यंत आधीपासूनच बेरीज करतो.

अंमलबजावणी

1 डी अ‍ॅरे लीटकोड सोल्यूशनच्या रनिंग योगासाठी सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

vector<int> runningSum(vector<int>& nums) 
{
    vector<int> res(nums.size());
    if(nums.size()==0) return res;

    res[0]=nums[0];
    for(int i=1;i<nums.size();i++)
    {
        res[i]=res[i-1]+ nums[i];
    }

    return res;

}

int main() 
{
  vector<int> nums={1,2,3,4};
  vector<int> res= runningSum(nums);
  
  cout<<"[";
  
  for(int i=0;i<res.size()-1;i++) cout<<res[i]<<",";
  
  cout<<res.back()<<"]"<<endl;

  return 0; 
}
[1,3,6,10]

1 डी अ‍ॅरे लीटकोड सोल्यूशनच्या रनिंग योगासाठी जावा प्रोग्राम

import java.lang.*;

class Rextester
{  
    public static int[] runningSum(int[] nums) 
    {
        int[] res= new int[nums.length];
        if(nums.length==0) return res;

        res[0]=nums[0];
        for(int i=1;i<nums.length;i++)
        {
            res[i]=res[i-1]+ nums[i];
        }

        return res;
    }
    
    public static void main(String args[])
    {
        int nums[]={1,2,3,4};
        int res[]= runningSum(nums);

        System.out.print("[");

        for(int i=0;i<res.length-1;i++) System.out.print(res[i]+",");

        System.out.println( res[res.length-1] + "]");
        
    }
}
[1,3,6,10]

1 डी अ‍ॅरे लीटकोड सोल्यूशनच्या चालू योगाकरिता जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन): जेथे एन दिलेली अ‍ॅरेचा आकार आहे. जसे आपण केवळ एका पळवाटसाठी चालत आहोत, त्यामुळे वेळ गुंतागुंत रेषात्मक होईल.

स्पेस कॉम्प्लेक्सिटी 

ओ (एन): येथे आपण n च्या आकाराचा रिझल्ट अ‍ॅरे बनवत आहोत. म्हणून अवकाश अवघडपणा देखील रेषात्मक असेल.