我正在尝试编写一个程序，其输入是整数数组，以及它的大小。这段代码必须删除每个小于左边元素的元素。
返回后的数组内容不重要，只关心返回值。
例如:给定数组[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;
}
我的代码工作，但我希望它更快。
你有什么办法让这段代码更快，或者其他比这更快的方法吗?
这是一个0 (NlogN)解。
这个想法是遍历数组并继续跟踪candidateKillers，这可能会杀死未访问的数字。然后，我们使用二分查找找到当前数的杀手，并在需要时更新最大迭代。
由于我们遍历有N个数字的数组，并对每个数字进行log(N)次二进制搜索，因此总体时间复杂度为O(NlogN)。
完成
-
如果当前数字大于或等于它之前的数字，它可能是一个杀手，对于它之后的数字。
-
对于每个杀手，我们持续跟踪它的索引
idx,num的数量以及到达杀手iters所需的迭代次数。 -
candidateKillers中的数字本质上是不增加的(见下一点)。因此，我们可以使用二分查找来找到当前数的杀手，即a)最接近当前数b)大于当前数的杀手。这在searchKiller中实现。 -
如果当前数量将被
candidateKillers中的数字与killerPos一起杀死，那么killerPos之后的所有候选杀手都是过时的，因为那些过时的杀手会在当前数量之后的数字到达之前被杀死。如果当前数量大于所有candidateKillers，则可以丢弃所有candidateKillers。 -
当我们找到当前编号的杀手时，我们将杀手的
iters加1。因为从现在开始，需要再进行一次迭代才能到达需要先杀死当前数量的杀手。
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
}
可以反向迭代，保留两个迭代器或索引并移动元素。您不需要分配一个新的矢量，甚至不需要调整现有矢量的大小。也是次要的，但可以用循环代替递归，或者按照编译器可能的方式编写代码。
这种方法仍然是O(n^2)的最坏情况，但在运行时间上会更快。