發現陣列

Question

這裏大多數occurence元素是簡單的程序來找到它最常出現的數組元素：

#include <cstdlib> 
#include <iostream> 
#include <vector> 

using namespace std; 

int main(int argc, char *argv[]) { 
    int a[] = {1,2,3,4,4,4,5}; 
    int n = sizeof(a)/sizeof(int); 
    int max = 0; 
    int result = 0; 
    int *b = new int[n]; 
    for (int i = 0; i < n; i++) { 
     b[a[i]] = (b[a[i]] || 0) + 1; 
     if (b[a[i]] > max) { 
      max = b[a[i]]; 
      result = a[i]; 
     } 
    } 
    cout << result << endl; 
    system("PAUSE"); 
    return EXIT_SUCCESS; 
} 

但它不工作;它打印1。爲什麼？

Answer 1

您需要將您的數組b初始化爲零。

b[a[i]]||0 

不會工作，你不知道b本來是什麼。

短代碼：

int main(int argc, char *argv[]) 
{ 
    int a[]={1,2,3,4,4,4,5}; 
    int n = sizeof(a)/sizeof(int); 
    int *b=new int [n]; 
    fill_n(b,n,0); // Put n times 0 in b 

    int val=0; // Value that is the most frequent 
    for (int i=0;i<n;i++) 
     if(++b[a[i]] >= b[val]) 
      val = a[i]; 

    cout<<val<<endl; 
    delete[] b; 
    return 0; 
} 

注意：如果最大值小於值的數組中的數量少 代碼（也是我的）才能發揮作用。

如果情況並非如此，並且最大值大於元素數量，則可能需要對數組進行排序，然後在線性時間（和恆定空間）內搜索最大值。

Answer 2

您尚未初始化您的陣列b。你可以這樣說：

int *b=new int [n](); 
        ^^ 

一旦做到這一點，你可以增加你的頻率排列爲：代替

b[a[i]]=(b[a[i]]||0)+1; 

你在做(b[a[i]]||0)+1作品的方式

b[a[i]]++; 

諸如Javascript，Perl這樣的語言，其中未初始化的數組元素將具有稱爲undef或null的特殊值。 C++沒有類似的東西，未初始化的數組將有垃圾。

Answer 3

既然你是包括向量，爲什麼不替換int *b=new int [n];與std::vector<int> b(n)？這也將照顧釋放內存，你忘了delete[] b。

但正如其他人所說，如果數組包含大於n的元素，您的解決方案將中斷。一個更好的方法可能是通過映射到int來計算元素。這樣，您還可以計算不能用作數組索引的元素，例如字符串。

也沒有理由限制自己陣列。下面是與任何低於可比元件類型的任何容器工作的通用的解決方案：

#include <algorithm> 
#include <iterator> 
#include <map> 

struct by_second 
{ 
    template <typename Pair> 
    bool operator()(const Pair& a, const Pair& b) 
    { 
     return a.second < b.second; 
    } 
}; 


template <typename Fwd> 
typename std::map<typename std::iterator_traits<Fwd>::value_type, int>::value_type 
most_frequent_element(Fwd begin, Fwd end) 
{ 
    std::map<typename std::iterator_traits<Fwd>::value_type, int> count; 

    for (Fwd it = begin; it != end; ++it) 
     ++count[*it]; 

    return *std::max_element(count.begin(), count.end(), by_second()); 
} 

#include <iostream> 
#include <vector> 

int main() 
{ 
    std::vector<int> test {1, 2, 3, 4, 4, 4, 5}; 
    std::pair<int, int> x = most_frequent_element(test.begin(), test.end()); 
    std::cout << x.first << " occured " << x.second << " times"; 
} 

Answer 4

這裏

，O（n）的時間，O（1）在上有序區間工作空間的一般解決方案。

#include <iostream> 

template <class ForwardIterator> 
ForwardIterator 
most_common(ForwardIterator first, ForwardIterator last) { 
    /** Find the most common element in the [first, last) range. 

     O(n) in time; O(1) in space. 

     [first, last) must be valid sorted range. 
     Elements must be equality comparable. 
    */ 
    ForwardIterator it(first), max_it(first); 
    size_t count = 0, max_count = 0; 
    for (; first != last; ++first) { 
    if (*it == *first) 
     count++; 
    else { 
     it = first; 
     count = 1; 
    }  
    if (count > max_count) { 
     max_count = count; 
     max_it = it; 
    } 
    } 
    return max_it; 
}  
int main() { 
    int a[] = {1, 2, 3, 4, 4, 4, 5}; 
    const size_t len = sizeof(a)/sizeof(*a); 
    std::cout << *most_common(a, a + len) << std::endl; 
} 

Answer 5

利用事實圖進行排序的實現。

#include <iostream> 
#include <vector> 
#include <map> 

using namespace std; 

template<class T> pair<T, int> getSecondMostOccurance(vector<T> & v) { 
    map<T, int> m; 

    for (int i = 0; i < v.size(); ++i) { 
     m[ v[i] ]++; 
    } 
    return *m.end(); 
} 

int main() { 
    int arr[] = {1, 4, 5, 4, 5, 4}; 
    pair<int, int> p = getSecondMostOccurance(vector<int>(arr, arr+7)); 
    cout << "element: " << p.first << " count: " << p.second << endl; 
    return 0; 
}