1d ارے لیٹکوڈ حل کی چلانے کا سم


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایڈوب ایمیزون ایپل بلومبرگ Uber
لڑی

مسئلہ یہ بیان

1d کی چلتی رقم میں صف مسئلہ ہمیں ایک صفی نمبر دی گئی ہے جس کے ل we ہمیں ایک صف واپس کرنا پڑے گی جہاں ہر ایک انڈیکس کے لئے نتیجہ سرنی میں [i] = رقم (اعداد [0]… اعداد [i]) ہوں۔

مثال کے طور پر

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

وضاحت:

چلانے کا حساب یہ ہے: [1، 1 + 2، 1 + 2 + 3، 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]

نقطہ نظر

اس پریشانی میں ہمیں ایک صف تیار کرنا ہوگی جہاں انڈیکس میں عنصر کی قیمت 1 سے لے کر آئتھ انڈیکسڈ عنصر کے برابر عناصر کے برابر ہو گی۔
اس کے لئے ہم دیئے گئے سرنی سائز کے برابر سائز کا ایک صف تیار کرسکتے ہیں۔ پھر لوپ کے ل a میں ہر عنصر کے ل we ہم عنصر انڈیکس 0 سے انڈیکس i میں اصل صف میں لوپ کے لئے دوسرا استعمال کرسکتے ہیں۔ اس الگورتھم کے لئے وقت کی پیچیدگی O (n ^ 2) ہوگی۔

ہم صرف ایک سنگل استعمال کر کے اس مسئلے کے لئے وقت کی پیچیدگی کو کم کرسکتے ہیں لوپ.
اعداد دیئے گئے سرنی بنیں اور ریز ایک صف بنیں جس میں ہم چلتی رقم جمع کررہے ہیں ، پھر ہم ریسزیو [i] کا حساب کتاب درج ذیل کے مطابق کرسکتے ہیں۔

res [i] = res [i-1] + نمبر [i]۔

مثال کے طور پر: نمبر = [1,2,3,4،XNUMX،XNUMX،XNUMX] ذیل کے اعداد و شمار میں دکھایا گیا ہے ،

1d ارے لیٹکوڈ حل کی چلانے کا سم

لہذا ہمیں ایک بار پھر سے ماقبل کا حساب کتاب کرنے کے لئے لوپ کو چلانے کی ضرورت نہیں ہے کیونکہ ہمارے پاس پہلے ہی انڈکس تک رقم ہے جو میں نے دوبارہ اشارے کے پچھلے انڈیکس میں ذخیرہ کیا ہے۔

عمل

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]

جاوا پروگرام برائے چلانے کا 1d ارے لیٹکوڈ حل

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 ڈی ارے لیٹ کوڈ حل کے چلانے کے لئے پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (n): جہاں n دیئے گئے صفوں کا سائز ہے۔ چونکہ ہم صرف ایک سنگل لوپ کے لئے چل رہے ہیں ، لہذا وقت کی پیچیدگی لکیری ہوگی۔

خلائی پیچیدگی 

O (n): یہاں ہم ن کے سائز کا نتیجہ سرنی پیدا کر رہے ہیں۔ لہذا خلائی پیچیدگی بھی لکیری ہوگی۔