給定一組N值都是0或X的，除了一個Y，找到X的最有效方法是什麼？

基本上我有一組冗餘數據可能會在一個值（一個或多個）中出現錯誤。一些值也可以是0，這意味着忽略/無效。什麼是回報「好」價值的最有效方法？給定一組N值都是0或X的，除了一個Y，找到X的最有效方法是什麼？

愚蠢的解決方案將是一個for循環遍歷該集合，並返回一旦找到兩個相同的非零值。但是我覺得可能會有一些邏輯/比特黑客表達會更好。

2012-07-11 Ian

你的數據如何存儲？什麼比例的清單是零？你有目標平臺/語言嗎？ – mfa 2012-07-11 18:54:50

也，類似的SO問題：http://stackoverflow.com/questions/1332527/what-are-the-fast-algorithms-to-find-duplicate-elements-in-a-collection-and-grou – mfa 2012-07-11 18:58:05

我'我實際上將這個作爲硬件來實現，所以我想我會盡可能地理論。但是我使用Verilog，如果你知道的話:)。沒有關於零的數量的假設。 – Ian 2012-07-11 19:16:11

'愚蠢的'解決方案可能是最好的解決方案，特別是在數據集中沒有多少零的情況下。在大多數情況下，你會很早就從環路中斷開。

如果硬件能夠快速掃描非零條目，在存在大量零的情況下，可以優化速度。我想在FPGA硬件上尋找非零非常容易，但我自己沒有親身體驗過這個。

來源

2012-07-11 19:52:08 mfa

給定一組N值都是0或X的，除了一個Y，找到X的最有效方法是什麼？

回答

相關問題