C++中的lambda函數在priority_queue中通過引用捕獲

Question

我正在解決一個算法問題 - 「找到第k個醜數」，下面是問題陳述和我的實現。

Write a program to find the n-th ugly number. 
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. 
For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers. 

vector<int> tmp(1,1); 
vector<int> primes({2,3,5}); 
vector<int> indices(3, 0); 
// lambda function pass in variables are captured by reference 
priority_queue<int, vector<int>, function<bool(const int&, const int&)>> pq([&](const int& a, const int& b){ 
    return primes[a] * tmp[indices[a]] > primes[b] * tmp[indices[b]]; 
}); 
pq.push(0); pq.push(1); pq.push(2); 
while(tmp.size() <= 3) { // find the first three ugly number 
    int primeIndex = pq.top(); 
    pq.pop(); 
    int nextval = primes[primeIndex] * tmp[indices[primeIndex]]; 
    pq.push(primeIndex + 1); 
    indices[primeIndex]++; 

    while(!pq.empty() && primes[pq.top()] & tmp[indices[pq.top()]]) { 
     primeIndex = pq.top(); 
     pq.pop(); 
     pq.push(primeIndex + 1); 
     indices[primeIndex]++; 
    } 
    cout << nextval << endl; 
    tmp.push_back(nextval); 
} 
return 0; 

priority_queue的用法是對此解決方案的優化。 Priority_queue在O（logN）時間中找到「下一個醜陋」數字。 priority_queue使用primes []的索引作爲其元素。它使用lambda函數作爲比較器，並通過引用捕獲所有外部變量。我測試了我的代碼以輸出前3個難看的數字（應該是2,3,4），但是我的代碼給了我「2,6,0」。我認爲在priority_queue中我的lambda函數有些問題，但我找不到原因。任何人都可以給我一個解決我的錯誤的提示嗎？非常感謝你。

Answer 1

您的代碼的直接問題是您正在訪問tmp向量越界。您使用indices的元素作爲tmp的索引，並且您可以在outer while循環的迭代中的多個位置（內部while循環之前的一次以及潛在的一次或多次內部while循環內）中增加indices的元素，以及在外循環的迭代結束時，只增加tmp的大小。與此同時，在內部while循環的情況下，您可以用tmp索引來指示您可能已增加（可能多次）的索引，然後再增大tmp的大小。