Оптимізація часу виконання коду за допомогою .size() у C++

7 Березня 2024 в 18:28 21

Під час вирішення задач на платформі LeetCode або у будь-якому іншому проекті, де кожна мілісекунда рахується, оптимізація часу виконання коду є критично важливою. В одному з таких випадків, я відзначив певну динаміку часу під час вирішення задачі LeetCode 27. В якості прикладу розглянемо проблему видалення елементів з масиву в C++ за допомогою .size().

У вищенаведеному коді ми бачимо клас Solution, який містить метод removeElement, що приймає масив nums і значення val. Мета цього методу – видалити всі входження val в масиві nums та повернути кількість елементів, які залишилися після видалення. Перший пример коду працює з проблемою, яка може виникнути під час використання .size() без оптимізації.

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int count=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==val){
                for(int j=i;j+1<nums.size();j++){
                    nums[j]=nums[j+1];
                    count+=1;
                }
                i--;
            }
        }
        return nums.size()-count;
    }
};

class Solution {

public:

int removeElement(vector<int>& nums, int val) {

int count=0;

for(int i=0;i<nums.size();i++){

if(nums[i]==val){

for(int j=i;j+1<nums.size();j++){

nums[j]=nums[j+1];

count+=1;

}

i--;

}

return nums.size()-count;

}

};

Проблема з цим кодом полягає у вкладеному циклі, який має часову складність O(n^2), де n – це розмір масиву nums. Кожен раз, коли ми видаляємо елемент з масиву, всі наступні елементи зсуваються на одну позицію вліво, що призводить до додаткових обробок усіх наступних елементів масиву, що призводить до додаткового часу виконання.

У другому прикладі ми вирішуємо цю проблему, використовуючи оптимізований підхід. Ми записуємо розмір масиву nums у змінну size та використовуємо її як умову циклу. Таким чином, ми уникнемо зайвих обробок елементів масиву після його скорочення.

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int count=0,size=nums.size();
        for(int i=0;i<size;i++){
            if(nums[i]==val){
                for(int j=i;j+1<size;j++){
                    nums[j]=nums[j+1];
                    count+=1;
                }
                i--;
                size--;
            }
        }
        return size;
    }
};

class Solution {

public:

int removeElement(vector<int>& nums, int val) {

int count=0,size=nums.size();

for(int i=0;i<size;i++){

if(nums[i]==val){

for(int j=i;j+1<size;j++){

nums[j]=nums[j+1];

count+=1;

}

i--;

size--;

}

return size;

}

};

Цей підхід дозволяє нам значно зменшити час виконання коду за рахунок уникнення зайвих обробок елементів масиву та зменшення вкладеності циклів, що призводить до оптимізації часової складності алгоритму.

Незважаючи на те, що обидва приклади коду досягають однакового результату, оптимізований підхід використання .size() дозволяє нам уникнути зайвих обчислень та зменшити час виконання коду, що може бути критично важливим у великих проектах або при вирішенні задач на часовій обмеженій платформі, такій як LeetCode.