從系列中查找唯一的數字而不會中斷

-2

我是stackoverflow的新手。請幫助我，如果它的轉職。我是C++/STL開發人員，正在尋找：從系列中查找唯一的數字而不會中斷

從整數序列中找出唯一編號，但不改變其順序。例如：i/p：10,4,3,6,1,0,4,4,4,10,5,9,0,6,15，... o/p（預期結果）：10， 4,3,6,1,0,5,9,15，...

約束： - 時間複雜性不應該是最差（N^2）。需要在更短的時間內解決它。 - 記憶足夠。 - appricieate，如果你可以解釋一下STL容器或算法，我必須用它來解決這個問題。

我試過使用unorder_set，但它打亂了排序，所以有點困惑。

來源

2015-04-07 vicky

你能展示你試過的算法嗎？ – caveman

O（N）內存：複製，排序，唯一 –

問題最適合http://cs.stackexchange.com/ – jean

您可以使用std :: unordered_map：

#include <iostream> 
#include <vector> 
#include <unordered_map> 

int main() { 
std::unordered_map<int, int> mynums; 
std::vector<int> myvect = {10,4,3,6,1,0,4,4,4,10,5,9,0,6,15}; 
for (auto myelem: myvect) { 
    mynums[myelem]++; 
} 
for (auto myelem: mynums) { 
    if (myelem.second > 1) { 
    std::cout << "Value "<<myelem.first << " " << myelem.second << " times" <<std::endl; 
    } 
} 
return 0; 
}

該方法僅打印的repetetive號碼，並應具有攤銷O（n）的複雜性。

這將是你的興趣，然後將如下的代碼如下：

#include <iostream> 
#include <vector> 
#include <unordered_map> 

int main() { 
std::unordered_map<int, int> mynums; 
std::vector<int> myvect = {10,4,3,6,1,0,4,4,4,10,5,9,0,6,15}; 
for (auto myelem: myvect) { 
    if (mynums[myelem] == 0) { 
     std::cout << myelem << ","; 
    } 
    mynums[myelem]++; 
} 

return 0; 
}

來源

2015-04-07 11:33:38

thnx。我認爲我們可以在這兩個環節中分享。 1.可以線性橫斷向量和一個循環 2.調用unorder_set :: find（myelem）。如果不。發現然後忽略 3. else將myelem存儲在unordered_set中這將以O（nlogn）複雜度完成作業，但在一個循環內完成。在你的邏輯中，它會遍歷循環兩次，雖然在你的情況下複雜性看起來更好O（n）。 Wat你說？ – vicky

是的，它將給予分期付款的O（n），因爲插入和對unordered_map的訪問是攤銷O（1）。 –

您可以使用std::unique，然後添加resize調整您vector（或其他容器）：

auto it = myvector.begin(); 
it = unique (myvector.begin(), myvector.end());                 
myvector.resize(distance(myvector.begin(),it));

來源

2015-04-07 11:33:48 VVG

這隻適用於價值排序，情況並非如此 –

@VVG - 我懷疑它會維持秩序。你能解釋一下它是如何工作的嗎？即使不確定獨特的時間複雜性和調整大小和距離。請提及這一點。 – vicky

@VGG：時間複雜度：排序：O（n log n）;獨特：O（n）;距離：O（1）;調整大小：O（N）...但是，再次，這是你應該能夠研究自己，像在谷歌 –

O(n²)中的天真做法：

std::vector<int> find_unique_numbers(const std::vector<int>& v) 
{ 
    std::vector<int> res; 

    for (auto e : v) { 
     if (std::find(res.begin(), res.end(), e) == res.end()) { 
      res.push_back(e); 
     } 
    } 
    return res; 
}

Live demo

來源

2015-04-07 12:19:49 Jarod42

從系列中查找唯一的數字而不會中斷

回答

相關問題