使用雙數組來查找模式？

我被困在如何編寫一個函數，該函數可以使用該數組及其長度作爲參數來查找數組中包含的一組整數的模式或模式。我已經找到了多種解決方案，可以找到如何查找數組模式，但我試圖通過以下方式解決此問題：使用雙數組來查找模式？

假設原始數組包含（0，0，1，5，5 ，5，7，7，7）。我想通過循環遍歷數組，找到任何數量的最高頻率而不存儲模式，並將這些頻率存儲在另一個數組中，在這種情況下，新數組將具有值（1，2，1， 1，2，3，1，2，3）。通過查找第二個數組中的最大值，我會發現最高頻率，在這種情況下爲3。然後，我想再次遍歷原始數組，將最高頻率與該數組中每個值的計數進行比較，並在匹配的位置處返回該值，在此示例中爲5和7給予。根據這裏的標準，您將如何編寫此函數來查找給定數組的模式？（你可以假設數組已經按照升序排序）。

編輯：這是我的初步代碼。我可以找到原始數組中每個整數的頻率並將它們存儲到另一個數組中的步驟。

void findMode(int array, int size){ 
     int count = 1; 
     int freq[size]; 
     freq[0] = count; 
     for (int pass = 1; pass < size; pass++){ 
      if (array[pass] == array[pass-1]){ 
      count++; 
      freq[pass] = count; 
      } 
      else{ 
       count = 1; 
       freq[pass] = count; 
       } 
     }

來源

2017-02-22 Amos Wu

'的std ::排序（array.begin（），array.end（））;'他們首先，然後迭代。 –

如何使用具有鍵的映射作爲其整數和值作爲其發生的映射。每當您再次看到相同的密鑰時，就增加該值。雖然我不確定如何確定最大值，除非您重複整個事情。編輯：這裏的問題顯示了同樣的事情http://stackoverflow.com/a/9370990/1083027只是保持運行計數最大 –

等等，你爲什麼要這個？爲什麼不保留列表中等於列表中最高數字的值的列表，並且如果發現一個高於max的值，就將其擦除？ –

如果你不介意一些額外的存儲空間（潛在O(N)存儲），你可以使用一個std::map獲得計數，然後最頻繁的數量線性搜索。

#include <algorithm> 
#include <cstddef> 
#include <iostream> 
#include <map> 
#include <vector> 

template<class InputIterator> 
auto mode(InputIterator first, InputIterator last) 
{ 
    using key_type = typename std::iterator_traits<InputIterator>::value_type; 
    std::map<key_type, std::size_t> counts; 
    for (auto it = first; it != last; ++it) { 
     counts[*it]++;  
    }  
    return *std::max_element(counts.cbegin(), counts.cend(), [](auto const& lhs, auto const& rhs) { 
     return lhs.second < rhs.second; 
    }); // return mode + frequency 
} 

int main() { 
    auto v = std::vector<int> { 0, 0, 1, 5, 5, 5, 7, 7, 7 }; 
    auto m = mode(v.cbegin(), v.cend()); 
    std::cout << m.first << ": " << m.second; 
}

Live Example //輸出5:3

來源

2017-02-22 16:44:51 TemplateRex

使用雙數組來查找模式？

回答

相關問題