1 डी ऐरे लेटकोड सॉल्यूशन का रनिंग सम


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना सेब ब्लूमबर्ग Uber
ऐरे

समस्या का विवरण

1 डी चलाने में सरणी समस्या हमें एक सरणी संख्या दी गई है जिसके लिए हमें एक सरणी वापस करनी होगी जहां परिणाम सरणी में प्रत्येक सूचकांक i के लिए गिरफ्तार किया गया [i] = sum (संख्या [0] ... nums [i])।

उदाहरण

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

स्पष्टीकरण:

रनिंग योग है: [१, १ + २, १ + २ + ३, १ + २ + ३ + ४] = [१, ३, ६, १०]

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

स्पष्टीकरण:

रनिंग योग है: [1, 1 + 1, 1 + 1 + 1, 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1] = [1, 2, 3, 4, 5]

दृष्टिकोण

इस समस्या में हमें एक ऐसी सारणी बनानी होगी जहाँ सूचकांक में तत्व का मान दिए गए सरणी में पहली से ith अनुक्रमित तत्व के योग के बराबर होगा।
इसके लिए हम बस दिए गए सरणी आकार के बराबर एक सरणी बना सकते हैं। फिर लूप के लिए प्रत्येक तत्व के लिए हम इंडेक्स 0 से इंडेक्स i तक के तत्व को मूल सरणी में लूप के लिए दूसरे का उपयोग करके जोड़ सकते हैं। इस एल्गोरिथ्म के लिए समय जटिलता O (n ^ 2) होगी।

हम केवल एकल का उपयोग करके इस समस्या के लिए समय की जटिलता को कम कर सकते हैं पाश.
अंक को दिए गए एरे के रूप में दें और एक एरे बनें, जिसमें हम रनिंग राशि जमा कर रहे हैं, तो हम रेस [i] की गणना कर सकते हैं:

res [i] = res [i-1] + nums [i]।

उदाहरण: अंक = [१,२,३,४] नीचे चित्र में दिखाया गया है,

1 डी ऐरे लेटकोड सॉल्यूशन का रनिंग सम

इसलिए हमें फिर से उपसर्ग राशि की गणना करने के लिए लूप के लिए दौड़ने की आवश्यकता नहीं है क्योंकि हमारे पास पहले से ही है, जब तक कि रिज़ॉर्ट सरणी के पिछले इंडेक्स में संग्रहीत I इंडेक्स तक नहीं है।

कार्यान्वयन

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 दिए गए सरणी का आकार है। जैसा कि हम लूप के लिए केवल एक ही चल रहे हैं, इसलिए समय जटिलता रैखिक होगी।

अंतरिक्ष जटिलता 

पर) : यहां हम n के आकार का परिणाम सरणी बना रहे हैं। इसलिए अंतरिक्ष की जटिलता भी रैखिक होगी।