我正在嘗試撰寫一個程式，其輸入是一個整數陣列及其大小。此代碼必須洗掉每個小于左側元素的元素。我們想找到我們可以以這種方式處理陣列的次數，直到我們不能再洗掉任何元素為止。
我們回傳后陣列的內容并不重要——只有回傳值才是有意義的。
例如：給定陣列[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;
}
我的代碼有效，但我希望它更快。
您是否有任何想法使此代碼更快，或者其他比這更快的方法？
uj5u.com熱心網友回復：
您可以反向迭代，保持兩個迭代器或索引和移動元素就位。您不需要分配新向量，甚至不需要調整現有向量的大小。也是次要的，但可以用回圈替換遞回或以編譯器可能的方式撰寫代碼。
這種方法仍然是 O(n^2) 最壞的情況，但它在運行時會更快。
uj5u.com熱心網友回復：
這是一個 O(NlogN) 解決方案。
這個想法是迭代陣列并保持跟蹤candidateKillers可能會殺死未訪問過的數字。然后我們使用二分搜索找到當前的殺手并更新最大迭代次數。
由于我們遍歷具有 N 個數字的陣列并對每個數字應用 log(N) 二進制搜索，因此總時間復雜度為 O(NlogN)。
演算法
如果當前數字大于或等于它之前的數字，則它可能是它之后的數字的殺手。
對于每個殺手，我們會不斷跟蹤其索引
idx、數量num以及達到該殺手所需的迭代次數iters。中的數字
candidateKillers本質上是不增加的（見下一點）。因此，我們可以應用二分查找來找到當前數字的殺手，即 a) 最接近當前數字 b) 大于當前數字的殺手。這是在searchKiller.如果當前的數量將由數量被殺害
candidateKillers用killerPos，那么所有候選殺手后killerPos已經過時，因為目前數后的數字達到他們之前那些過時的殺手會被殺死。如果當前數大于 allcandidateKillers，則candidateKillers可以丟棄all 。當我們找到當前編號的殺手時，我們將殺手的數量加
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
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/337673.html