العثور على تكرار الأرقام في مجموعة معينة من الأرقام

Question

لنفترض أن لدينا متجهًا/مصفوفة في لغة C++ ونرغب في حساب أي من هذه العناصر N لديه الحد الأقصى من التكرارات المتكررة وإخراج أعلى عدد.ما هي الخوارزمية الأنسب لهذه المهمة؟

مثال:

int a = { 2, 456, 34, 3456, 2, 435, 2, 456, 2}

الناتج هو 4 لأن 2 يحدث 4 مرات.هذا هو الحد الأقصى لعدد مرات حدوث 2.

Answer 1

قم بفرز المصفوفة ثم قم بإجراء تمريرة سريعة لحساب كل رقم.تحتوي الخوارزمية على تعقيد O(N*logN).

وبدلاً من ذلك، قم بإنشاء جدول تجزئة باستخدام الرقم كمفتاح.قم بتخزين عداد في جدول التجزئة لكل عنصر قمت بربطه.ستتمكن من حساب جميع العناصر في تمريرة واحدة؛ومع ذلك، يعتمد تعقيد الخوارزمية الآن على مدى تعقيد وظيفة التوزيع الخاصة بك.

Answer 2

الأمثل للمساحة:

الفرز السريع (على سبيل المثال) ثم التكرار على العناصر، وتتبع العدد الأكبر فقط.في أحسن الأحوال O(N log N).

الأمثل للسرعة:

قم بالتكرار على كافة العناصر، وتتبع الأعداد المنفصلة.ستكون هذه الخوارزمية دائمًا O(n).

Answer 3

إذا كان لديك ذاكرة الوصول العشوائي (RAM) ولم تكن قيمك كبيرة جدًا، فاستخدمها فرز العد.

Answer 4

يمكن أن يكون تطبيق C++ المحتمل الذي يستخدم STL:

#include <iostream>
#include <algorithm>
#include <map>

// functor
struct maxoccur
{
    int _M_val;
    int _M_rep;

    maxoccur()
    : _M_val(0),
      _M_rep(0)
    {}

    void operator()(const std::pair<int,int> &e)
    {
        std::cout << "pair: " << e.first << " " << e.second << std::endl;
        if ( _M_rep < e.second ) {
            _M_val = e.first;
            _M_rep = e.second;
        }
    }
};

int
main(int argc, char *argv[])
{
    int a[] = {2,456,34,3456,2,435,2,456,2};
    std::map<int,int> m; 

    // load the map
    for(unsigned int i=0; i< sizeof(a)/sizeof(a[0]); i++) 
        m [a[i]]++;

    // find the max occurence...
    maxoccur ret = std::for_each(m.begin(), m.end(), maxoccur());
    std::cout << "value:" << ret._M_val << " max repetition:" << ret._M_rep <<  std::endl;

    return 0;
}

Answer 5

قليلاً من الكود الزائف:

//split string into array firts
strsplit(numbers) //PHP function name to split a string into it's components
i=0
while( i < count(array))
 {
   if(isset(list[array[i]]))
    {
      list[array[i]]['count'] = list + 1
    }
   else
    {
      list[i]['count'] = 1
      list[i]['number']
    }
   i=i+1
 }
usort(list) //usort is a php function that sorts an array by its value not its key, Im assuming that you have something in c++ that does this
print list[0]['number'] //Should contain the most used number

Answer 6

تعد خوارزمية التجزئة (عدد البناء[i] = #occurrences(i) في الوقت الخطي بشكل أساسي) عملية للغاية، ولكنها من الناحية النظرية ليست O(n) بشكل صارم لأنه قد يكون هناك تصادمات تجزئة أثناء العملية.

هناك حالة خاصة مثيرة للاهتمام لهذا السؤال وهي خوارزمية الأغلبية، حيث تريد العثور على عنصر موجود في n/2 على الأقل من إدخالات المصفوفة، في حالة وجود أي عنصر من هذا القبيل.

هنا أ شرح سريع, ، و أ شرح أكثر تفصيلا حول كيفية القيام بذلك في وقت خطي، دون أي نوع من الخداع.

Answer 7

إذا كان نطاق العناصر كبيرًا مقارنة بعدد العناصر، فسأقوم، كما قال الآخرون، بالفرز والمسح فقط.هذا هو الوقت n*log n ولا توجد مساحة إضافية (ربما سجل n إضافي).

المشكلة في فرز العد هي أنه إذا كان نطاق القيم كبيرًا، فقد يستغرق الأمر وقتًا أطول لتهيئة مصفوفة العد بدلاً من الفرز.

Answer 8

إليكم الإصدار الكامل والمختبر باستخدام std::tr1::unordered_map.

أقوم بهذا تقريبًا O(n).أولاً، يتكرر من خلال قيم الإدخال n لإدراج/تحديث الأعداد في ملف unordered_map, ، ثم يقوم ب partial_sort_copy وهو يا (ن).2*يا(ن) ~= يا(ن).

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

namespace {
// Only used in most_frequent but can't be a local class because of the member template
struct second_greater {
    // Need to compare two (slightly) different types of pairs
    template <typename PairA, typename PairB>
    bool operator() (const PairA& a, const PairB& b) const
        { return a.second > b.second; }
};
}

template <typename Iter>
std::pair<typename std::iterator_traits<Iter>::value_type, unsigned int>
most_frequent(Iter begin, Iter end)
{
    typedef typename std::iterator_traits<Iter>::value_type value_type;
    typedef std::pair<value_type, unsigned int> result_type;

    std::tr1::unordered_map<value_type, unsigned int> counts;

    for(; begin != end; ++begin)
        // This is safe because new entries in the map are defined to be initialized to 0 for
        // built-in numeric types - no need to initialize them first
        ++ counts[*begin];

    // Only need the top one at this point (could easily expand to top-n)
    std::vector<result_type> top(1);

    std::partial_sort_copy(counts.begin(), counts.end(),
                           top.begin(), top.end(), second_greater());

    return top.front();
}

int main(int argc, char* argv[])
{
    int a[] = { 2, 456, 34, 3456, 2, 435, 2, 456, 2 };

    std::pair<int, unsigned int> m = most_frequent(a, a + (sizeof(a) / sizeof(a[0])));

    std::cout << "most common = " << m.first << " (" << m.second << " instances)" << std::endl;
    assert(m.first == 2);
    assert(m.second == 4);

    return 0;
}

Answer 9

سيكون في O (ن) ...........ولكن الشيء هو لا كبيرة.من المصفوفة يمكن أن تأخذ مصفوفة أخرى بنفس الحجم ...........

ل(i=0;i

mar=count[o];مؤشر = س؛

ل(i=0;i

فيكون الناتج ..........العنصر فِهرِس حدث ل الأعلى لا.مرات في هذه المجموعة ........

هنا [] هي مصفوفة البيانات حيث نحتاج إلى البحث عن الحد الأقصى لحدوث رقم معين.في مصفوفة.......

العد [] وجود عدد كل عنصر ..........ملحوظة :نحن نعلم أن نطاق البيانات سيكون في المصفوفة ..يقول على سبيل المثال.تتراوح البيانات الموجودة في تلك المجموعة من 1 إلى 100 .......ثم اجعل مصفوفة العد مكونة من 100 عنصر لتتبعها، وإذا حدث ذلك قم بزيادة القيمة المفهرسة بمقدار واحد........