Может ли кто-нибудь помочь мне сократить сложность следующего кода? - PullRequest
Новая
       85

Может ли кто-нибудь помочь мне сократить сложность следующего кода?

0 голосов
/ 21 сентября 2019

Я новичок в хакерранке.Я всегда предпочитаю кодировать, не выходя за решение.Таким образом я получил эту проблему, так как мой код (приведенный ниже) получает требуемый вывод, но для больших входных данных он не выполняется в течение срока.Так что кто-нибудь поможет мне сократить время сложности.Также скажите мне, что кодирование без поиска решения - это хорошо или плохо ... 

long arrayManipulation(int n,int m, vector<vector<int>> q) {
    long result=0;
vector<long> arr(n,0);

for(long i=0;i<m;i++)
{
    for(long t=q[i][0];t<=q[i][1];t++)
    {
        arr[t-1]+=q[i][2];
    }

}

for(long i=0;i<n;i++)
{
    if(result<arr[i])
    {result=arr[i];}
}

return result;
}

Эти семь тестовых случаев не проходят

1 Ответ

0 голосов
/ 21 сентября 2019

Это может быть уменьшено: 

vector<long> arr(n,0);
for(long i=0;i<m;i++)
{
    for(long t=q[i][0];t<=q[i][1];t++)
    {
        arr[t-1]+=q[i][2];
    }

}

до чего-то вроде: 

vector<long> arr(n + 1,0);  // n+1 needed because q[i][1] can be n-1
for(long i=0;i<m;i++)
{
    arr[q[i][0]] += q[i][2];
    arr[q[i][1] + 1] -= q[i][2];
}
long sum = 0;
for(long i=0;i<m;i++) {
    sum += arr[i];
    arr[i] = sum;
}

Это работает, потому что, например, пусть a := [0, 0, 0, 0, 0], и вы хотите добавить 5 для элементов начальногомассив со 2-го по 4-й (не включен), затем вы можете сделать a[1] += 5, a[3] -= 5 (a is [0, 5, 0, -5, 0]) и затем вычислить суммы префиксов для a, это будет то, сколько вам нужно добавить ккаждый элемент вашего исходного массива (в данном случае [0, 5, 5, 0, 0]).

...