История изменений

Исправление former_anonymous, 30.03.25 20:54 (текущая версия) :

Задача https://leetcode.com/problems/longest-consecutive-sequence

Локальный код:

#include <vector>
#include <unordered_set>

using namespace std;

int longestConsecutive(const vector<int>& nums) {
    unordered_set<int> set;

    for (auto n : nums) {
        set.insert(n);
    }

    int longest = 0;

    // Итерация по nums медленнее чем по 'set' !!!
    for (auto n : nums) {
        // Start of a chain
        if (set.find(n - 1) == set.end()) {
            int length = 0;
            while (set.find(n + length) != set.end()) {
                length++;
            }
            longest = max(longest, length);
        }
    }

    return longest;
}

Тест:

nums содержит 50’000 элементов https://pastebin.com/diqtqMP4

Время отработки с nums в for - порядка 5000 мс на моём ПК.

Время отработки с set в for - порядка 10 мс на моём ПК.

Код main на Qt:


int main(int argc, char *argv[])
{
    const vector<int> nums = ...

    qint64 v = QDateTime::currentMSecsSinceEpoch();

    int longest = longestConsecutive(nums);

    qDebug() << nums.size() << longest << QDateTime::currentMSecsSinceEpoch() - v;

    return 0;
}

Исправление former_anonymous, 30.03.25 20:50:

Задача https://leetcode.com/problems/longest-consecutive-sequence

Локальный код:

#include <vector>
#include <unordered_set>

using namespace std;

int longestConsecutive(const vector<int>& nums) {
    unordered_set<int> set;

    for (auto n : nums) {
        set.insert(n);
    }

    int longest = 0;

    for (auto n : nums) {
        // Start of a chain
        if (set.find(n - 1) == set.end()) {
            int length = 0;
            while (set.find(n + length) != set.end()) {
                length++;
            }
            longest = max(longest, length);
        }
    }

    return longest;
}

Тест:

nums содержит 50’000 элементов https://pastebin.com/diqtqMP4

Время отработки с nums в for - порядка 5000 мс на моём ПК.

Время отработки с set в for - порядка 10 мс на моём ПК.

Код main на Qt:


int main(int argc, char *argv[])
{
    const vector<int> nums = ...

    qint64 v = QDateTime::currentMSecsSinceEpoch();

    int longest = longestConsecutive(nums);

    qDebug() << nums.size() << longest << QDateTime::currentMSecsSinceEpoch() - v;

    return 0;
}

Исходная версия former_anonymous, 30.03.25 20:41:

Задача https://leetcode.com/problems/longest-consecutive-sequence

Локальный код:

#include <vector>
#include <unordered_set>

using namespace std;

int longestConsecutive(const vector<int>& nums) {
    unordered_set<int> set;

    for (auto n : nums) {
        set.insert(n);
    }

    int longest = 0;

    for (auto n : nums) {
        // Start of a chain
        if (set.find(n - 1) == set.end()) {
            int length = 0;
            while (set.find(n + length) != set.end()) {
                length++;
            }
            longest = max(longest, length);
        }
    }

    return longest;
}

Тест:

nums содержит 50’000 элементов https://pastebin.com/diqtqMP4

Время отработки с nums в for - порядка 5000 мс на моём ПК.

Время отработки с set в for - порядка 10 мс на моём ПК.

Код на Qt:


int main(int argc, char *argv[])
{
    const vector<int> nums = ...

    qint64 v = QDateTime::currentMSecsSinceEpoch();

    int longest = longestConsecutive(nums);

    qDebug() << nums.size() << longest << QDateTime::currentMSecsSinceEpoch() - v;

    return 0;
}