Тот же код получает Time Out из-за оператора if в LeetCode - PullRequest
Новая
       37

Тот же код получает Time Out из-за оператора if в LeetCode

0 голосов
/ 04 мая 2020

Вопрос взят из LeetCode, в котором мы должны выяснить, есть ли в массиве два разных индекса i и j, так что абсолютное различие между nums [i] и nums [j] равно не более t , а абсолютная разница между i и j составляет не более k . Мой подход O (N * N), который не должен быть приемлемым, но это так.

Принятый код: 

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
    int n = nums.size();
    vector<pair<long long, int>>list;
    for (int i = 0; i < n; i++)
        list.push_back(make_pair(nums[i], i));
    sort(list.begin(), list.end());
    for (int i = 0; i < n-1; i++) {
        for (int j = i+1; j < n && list[j].first-list[i].first <= t; j++)
            if (abs(list[j].second - list[i].second) <= k)
                return true;
    }

    return false;
}

Код, который дает время ожидания: 

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
    int n = nums.size();
    vector<pair<long long, int>>list;
    for (int i = 0; i < n; i++)
        list.push_back(make_pair(nums[i], i));
    sort(list.begin(), list.end());
    for (int i = 0; i < n-1; i++) {
        for (int j = i+1; j < n ; j++)
            if(list[j].first-list[i].first <= t)
                if (abs(list[j].second - list[i].second) <= k)
                    return true;
    }

    return false;
}

Я не понимаю, почему первый код работает эффективно (согласно leetcode), а второй дает TLE? Единственное отличие заключается в использовании условного оператора «IF» внутри l oop, что, я думаю, не очень дорого.

Ссылка на вопрос: https://leetcode.com/problems/contains-duplicate-iii/

1 Ответ

5 голосов
/ 04 мая 2020

Если мы сводим это к основному, вы сравниваете 

for (int i = 0; i < imax; ++i) {
   if ( some_condition(i) ) {
       // do something
   }
}

против 

for (int i = 0; i < imax && some_condition(i); ++i) {
    // do something
}

Второй l oop заканчивается один раз some_condition(i) равен false, в то время как первый всегда выполняет все итерации.

Код очень непростителен, если вы неряшливы и не обращаете внимания на детали:

Единственное отличие - использование условного "IF" "утверждение внутри l oop

Нет, это не единственная разница!

...