Блог

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

Содержимое массива после нашего возврата не имеет значения — представляет интерес только возвращаемое значение.

Например: учитывая массив [10, 9, 7, 8, 6, 5, 3, 4, 2, 1] , функция должна возвращать 2, потому что:

[10,9,7,8,6,5,3,4,2,1] → [10,8,4] → [10]

Например: учитывая массив [1,2,3,4] , функция должна возвращать 0, потому что ни один элемент не больше элемента справа от него

Я хочу, чтобы каждый элемент удалял нужный элемент, если он больше, чем его правильный элемент. Мы получаем меньший массив. Затем мы снова повторяем эту операцию. Пока мы не доберемся до массива, в котором ни один элемент не сможет удалить другой элемент. Я хочу рассчитать количество выполненных шагов.

 int Mafia(int n, vector <int> input_array)
{
    int ptr = n;
    int last_ptr = n;
    int night_Count = 0;
    do
    {
        last_ptr = ptr;
        ptr = 1;
        for (int i = 1; i < last_ptr; i  )
        {
            if (input_array[i] >= input_array[i - 1])
            {
                input_array[ptr  ] = input_array[i];
            }
        }
        night_Count  ;
    } while (last_ptr > ptr);


    return night_Count - 1;
}
 

Мой код работает, но я хочу, чтобы он был быстрее.

У вас есть какие-либо идеи, как сделать этот код быстрее или другим способом, который быстрее, чем этот?

Вот решение O(NlogN).

Идея состоит в том, чтобы перебирать массив и продолжать отслеживать candidateKillers , что может привести к уничтожению незваных номеров. Затем мы находим убийцу для текущего числа с помощью двоичного поиска и при необходимости обновляем максимальное количество итераций.

Поскольку мы перебираем массив, содержащий N чисел, и применяем двоичный поиск по журналу(N) для каждого числа, общая временная сложность составляет O(NlogN).

Алогритм

• Если текущее число больше или равно числу до него, оно может стать убийцей для чисел после него.
• Для каждого убийцы мы продолжаем отслеживать его индекс idx , его количество num и итерации , необходимые для достижения этого убийцы iters .
• Числа в candidateKillers нем по своей природе не увеличиваются (см. Следующий пункт). Поэтому мы можем применить двоичный поиск, чтобы найти убийцу текущего числа, которое а) ближе всего к текущему числу б) больше текущего числа. Это реализовано в searchKiller .
• Если текущее число будет убито числом в candidateKillers с killerPos , то все кандидаты на убийство после killerPos устарели, потому что эти устаревшие убийцы будут убиты до того, как числа после текущего числа достигнут их. Если текущее число больше всех candidateKillers , то все candidateKillers они могут быть отброшены.
• Когда мы найдем убийцу текущего числа, мы увеличим iters число убийц на единицу. Потому что с этого момента требуется еще одна итерация, чтобы добраться до того убийцы, где сначала нужно убить текущее число.

 class Solution {
public:
    int countIterations(vector<int>amp; array) {
        if (array.size() <= 1) {
            return 0;
        }
        int ans = 0;
        vector<Killer> candidateKillers = {Killer(0, array[0], 1)};

        for (auto i = 1; i < array.size(); i  ) {
            int curNum = array[i];
  
            int killerPos = searchKiller(candidateKillers, curNum);
            if (killerPos == -1) {
                // current one is the largest so far and all candidateKillers before are outdated
                candidateKillers = {Killer(i, curNum, 1)};
                continue;
            }
            
            // get rid of outdated killers
            int popCount = candidateKillers.size() - 1 - killerPos;
            for (auto j = 0; j < popCount; j  ) {
                candidateKillers.pop_back();
            }
            
            Killer killer = candidateKillers[killerPos];
            ans = max(killer.iters, ans);
            
            if (curNum < array[i-1]) {
                // since the killer of the current one may not even be in the list e.g., if current is 4 in [6,5,4] 
                if (killer.idx == i - 1) {
                    candidateKillers[killerPos].iters  = 1;
                }
            } else {
                candidateKillers[killerPos].iters  = 1;
                candidateKillers.push_back(Killer(i, curNum, 1));   
            }

        }
        return ans;
    }
private:
    struct Killer {
        Killer(int idx, int num, int iters) 
            : idx(idx), num(num), iters(iters) {};
        int idx;
        int num;
        int iters;
    };
    
    int searchKiller(vector<Killer>amp; candidateKillers, int n) {
        int lo = 0;
        int hi = candidateKillers.size() - 1;
        if (candidateKillers[0].num < n) {
            return -1;
        }
        int ans = -1;
        while (lo <= hi) {
            int mid = lo   (hi - lo) / 2;
            if (candidateKillers[mid].num > n) {
                ans = mid;
                lo = mid   1;
            } else {
                hi = mid - 1;
            }
        }
        return ans;
    }
};


int main() {
    vector<int> array1 = {10, 9, 7, 8, 6, 5, 3, 4, 2, 1};
    vector<int> array2 = {1, 2, 3, 4};
    vector<int> array3 = {4, 2, 1, 2, 3, 3};



    cout << Solution().countIterations(array1) << endl; // 2
    cout << Solution().countIterations(array2) << endl; // 0
    cout << Solution().countIterations(array3) << endl; // 4
}

 

Вы можете выполнять итерацию в обратном порядке, сохраняя два итератора или индекса и перемещая элементы на месте. Вам не нужно выделять новый вектор или даже изменять размер существующего вектора. Также незначительный, но может заменить рекурсию циклом или написать код так, как это, скорее всего, сделает компилятор.

Этот подход по-прежнему является наихудшим случаем O(n^2), но он будет быстрее во время выполнения.