Покретање збира 1д низа Леетцоде решење


Ниво тешкоће Лако
Често питани у адобе амазонка јабука Блоомберг Убер
Ред

Изјава о проблему

У текућем збиру од 1д поредак проблем добили смо низ бројева за који морамо вратити низ где је за сваки индекс и у резултату низ арр [и] = зброј (нумс [0]… нумс [и]).

Пример

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

objašnjenje:

Текућа сума је: [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]

objašnjenje:

Текућа сума је: [1, 1 + 1, 1 + 1 + 1, 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1] = [1, 2, 3, 4, 5]

Приступ

У овом проблему морамо створити низ где ће вредност елемента у индексу и бити једнака збиру елемената од 1. до и-тог индексираног елемента у датом низу.
За ово можемо једноставно створити низ величине једнак датој величини низа. Тада за сваки елемент у фор петљи можемо додати елемент из индекса 0 у индекс и у оригиналном низу користећи другу фор петљу. Сложеност времена за овај алгоритам биће О (н ^ 2).

Сложеност времена за овај проблем можемо смањити коришћењем само једног петља.
нека су нумс задати низ, а рес низ у којем складиштимо текућу суму, тада можемо израчунати рес [и] на следећи начин:

рес [и] = рес [и-1] + бројеви [и].

пример: нумс = [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д низа Леетцоде решења

Сложеност времена

На) : где је н величина датог низа. Како покрећемо само једну фор петљу, стога ће временска сложеност бити линеарна.

Сложеност простора 

На) : Овде креирамо низ резултата величине н. Отуда ће сложеност простора такође бити линеарна.