მიმდინარეობს 1d მასივის Leetcode ამოხსნის ჯამის


Რთული ტური Easy
ხშირად ეკითხებიან Adobe Amazon Apple Bloomberg Uber
Array

პრობლემის განცხადება

გაშვებული ჯამი 1d მასივი პრობლემა მოგვცა მასივის ნომრები, რისთვისაც უნდა დავაბრუნოთ მასივი, სადაც თითოეული ინდექსისთვის i არის მასივი arr [i] = თანხა (nums [0]… nums [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]

მიდგომა

ამ პრობლემის დროს უნდა შევქმნათ მასივი, სადაც ელემენტის მნიშვნელობა i ინდექსში ტოლი იქნება მოცემული მასივის 1 – დან მე –XNUMX ინდექსირებული ელემენტის ჯამის.
ამისთვის შეგვიძლია უბრალოდ შევქმნათ ზომის მასივი, რომელიც მოცემულია მასივის ზომის ტოლი. შემდეგ for მარყუჟის თითოეული ელემენტისთვის ჩვენ შეგვიძლია დავამატოთ ელემენტი ინდექსი 0 – დან ინდექსში i– მდე თავდაპირველ მასივში სხვა მარყუჟის გამოყენებით. ამ ალგორითმის დროის სირთულე იქნება O (n ^ 2).

ამ პრობლემისთვის დროის სირთულის შემცირება შეგვიძლია მხოლოდ სინგლის გამოყენებით loop.
მოდით nums იყოს მოცემული მასივი და res იყოს მასივი, რომელშიც ჩვენ ვინახავთ გაშვებულ ჯამს, შემდეგ ჩვენ შეგვიძლია გამოვთვალოთ res [i] შემდეგნაირად:

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

მაგალითი: nums = [1,2,3,4] ნაჩვენებია ქვემოთ მოცემულ ფიგურაში,

მიმდინარეობს 1d მასივის Leetcode ამოხსნის ჯამის

ამრიგად, ჩვენ არ გვჭირდება აწარმოებს მარყუჟს for პრეფიქსით თანხის კვლავ გამოსათვლელად, რადგან ჩვენ უკვე გვაქვს ჯამი, სანამ ინდექსი ინახება res მასივის წინა ინდექსში.

განხორციელება

C ++ პროგრამა 1d მასივის Leetcode ამოხსნის ჯამის ამოსაღებად

#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]

Java პროგრამა 1d მასივის Leetcode ამოხსნის ჯამის გასაშვებად

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]

სირთულის ანალიზი 1d მასივის Leetcode ამოხსნის ჯამის ამოსაღებად

დროის სირთულე

O (n): სადაც n მოცემული მასივის ზომაა. რადგან ჩვენ მარყუჟისთვის მხოლოდ ერთს ვაწარმოებთ, ამიტომ დროის სირთულე ხაზოვანი იქნება.

სივრცის სირთულე 

O (n): აქ ჩვენ ვქმნით n შედეგის მასივს. შესაბამისად, სივრცის სირთულე ასევე ხაზოვანი იქნება.