时间戳

首页 > 解决方案 > 计算删除的迭代次数，直到数组被排序

c++ - 计算删除的迭代次数，直到数组被排序

问题描述

我正在尝试编写一个程序，其输入是整数数组及其大小。此代码必须删除每个小于左侧元素的元素。我们想找出我们可以以这种方式处理数组的次数，直到我们不能再删除任何元素。

我们返回后数组的内容并不重要——只有返回值是有意义的。

例如：给定数组[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;
}

我的代码有效，但我希望它更快。

您是否有任何想法使此代码更快，或者比这更快的其他方式？

标签： c++arraysalgorithmperformance

解决方案

这是一个 O(NlogN) 解决方案。

这个想法是遍历数组并继续跟踪candidateKillers可能会杀死未访问的数字。然后我们通过使用二进制搜索找到当前数字的杀手，并在需要时更新最大迭代次数。

由于我们遍历具有 N 个数字的数组并对每个数字应用 log(N) 二进制搜索，因此总体时间复杂度为 O(NlogN)。

算法

  • 如果当前数字大于或等于它之前的数字，它可能是它之后的数字的杀手。

  • 对于每个杀手，我们不断跟踪它的索引idx、它的数量num以及到达该杀手所需的迭代iters。

  • 就其性质而言，数字candidateKillers是不增加的（见下一点）。因此，我们可以应用二分查找来找到当前数的杀手，即 a) 最接近当前数 b) 大于当前数的那个。这是在searchKiller.

  • 如果当前号码会被candidateKillerswith中的号码杀死killerPos，那么后面的所有候选杀手killerPos都是过时的，因为那些过时的杀手会在当前号码后面的号码到达他们之前被杀死。如果当前数字大于 all candidateKillers，则candidateKillers可以丢弃所有的。

  • 当我们找到当前数字的杀手时，我们iters将杀手的加一。因为从现在开始，需要再进行一次迭代才能到达需要首先杀死当前数字的那个杀手。

class Solution {
public:
    int countIterations(vector<int>& 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>& 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
}

推荐阅读