ابحث عن الإدخال الأكثر شيوعًا في المصفوفة

Question

يتم منحك مصفوفة أعداد صحيحة غير موقعة 32 بت بطول يصل إلى 2³², ، مع خاصية أن أكثر من نصف الإدخالات في المصفوفة تساوي N، بالنسبة لبعض الأعداد الصحيحة غير الموقعة ذات 32 بت N.ابحث عن N بالنظر إلى كل رقم في المصفوفة مرة واحدة فقط واستخدام 2 كيلو بايت من الذاكرة على الأكثر.

يجب أن يكون الحل الخاص بك حتميًا ومضمونًا للعثور على N.

Answer 1

وحافظ على عدد صحيح واحد لكل بت، وزيادة هذه المجموعة بشكل مناسب لكل عدد صحيح في الصفيف.

وفي النهاية، بعض من البتات سوف يكون لها عدد أكبر من نصف طول المصفوفة - هذه البتات تحدد N. بطبيعة الحال، فإن العد سيكون أعلى من عدد المرات التي وقعت N، ولكن هذا لا شيء. الشيء المهم هو أن أي الشيء الذي ليس جزءا من N <م> لا يمكن تحدث أكثر من نصف مرات (لN لديها أكثر من نصف الإدخالات) وأي الشيء الذي هو جزء من N <م> يجب تحدث أكثر من نصف مرات (لأنها سوف تحدث في كل مرة يحدث N، وأي إضافات).

و(أي رمز في هذه اللحظة - على وشك أن تفقد وصول صافي نأمل أعلاه واضح بما فيه الكفاية على الرغم من)

Answer 2

بوير ومور "الخطي الوقت بالأغلبية خوارزمية" - النزول مجموعة الحفاظ على تخمين الحالي في الإجابة.

Answer 3

ويمكنك القيام بذلك مع متغيرات اثنين فقط.

public uint MostCommon(UInt32[] numberList)
{
    uint suspect = 0;
    int suspicionStrength = -1; 
    foreach (uint number in numberList)
    {
        if (number==suspect)
        {
            suspicionStrength++;
        }
        else
        {
            suspicionStrength--;
        }

        if (suspicionStrength<=0)
        {
            suspect = number;
        }
    }
    return suspect;
}

تأكد الرقم الأول عدد المشتبه، ومواصلة تنفيذ الحلقات عبر القائمة. إذا كان يطابق عدد، وزيادة قوة الشك تلو الآخر؛ إذا كان لا يطابق، وانخفاض القوة الشك تلو الآخر. إذا كانت قوة اشتباه يضرب 0 يصبح العدد الحالي عدد المشتبه. هذا سوف <م> لا العمل للعثور على العدد الأكثر شيوعا، سوى عدد التي هي أكثر من 50٪ من المجموعة. مقاومة الرغبة في إضافة الاختيار إذا suspicionStrength أكبر من نصف طول قائمة - أنه سيؤدي دائما في المزيد من اجمالي مقارنات

وP.S. أنا لم تختبر هذا الرمز - استخدامه على مسؤوليتك الخاصة

Answer 4

والزائفة الرمز (المفكرة C ++ :-)) لخوارزمية جون ل:

int lNumbers = (size_of(arrNumbers)/size_of(arrNumbers[0]);

for (int i = 0; i < lNumbers; i++)
  for (int bi = 0; bi < 32; bi++)
    arrBits[i] = arrBits[i] + (arrNumbers[i] & (1 << bi)) == (1 << bi) ? 1 : 0;

int N = 0;

for (int bc = 0; bc < 32; bc++)
  if (arrBits[bc] > lNumbers/2)
    N = N | (1 << bc);

Answer 5

لاحظ أنه إذا تسلسل a0, a1, . . . , an−1 يحتوي على الزعيم، ثم بعد إزالة زوج من عناصر من قيم مختلفة، وتسلسل المتبقية لا تزال لديه قائد واحد. في الواقع، إذا كنا إزالة عنصرين مختلفين ثم فقط واحد منهم يمكن أن يكون القائد. الرائدة في مجال تسلسل جديد يحدث أكثر من n/2 − 1 = (n−2)/2 مرات. وبناء على ذلك، فإنه لا يزال زعيم سلسلة جديدة من عناصر n − 2.

وهنا هو تطبيق بيثون، مع O (ن) تعقيد الوقت:

def goldenLeader(A):
    n = len(A)
    size = 0
    for k in xrange(n):
        if (size == 0):
            size += 1
            value = A[k]
        else:
            if (value != A[k]):
                size -= 1
            else:
                size += 1
    candidate = -1
    if (size > 0):
        candidate = value
    leader = -1
    count = 0
    for k in xrange(n):
        if (A[k] == candidate):
            count += 1
    if (count > n // 2):
        leader = candidate
    return leader

Answer 6

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

---

من الواضح أنه يمكنك التعامل معها من خلال التجزئة أو الفرز، ولكن مع التدفق غير المحدود المحتمل، فمن الواضح أن الذاكرة قد نفدت.لذلك عليك أن تفعل شيئًا ذكيًا هنا.

---

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

لذا، إذا قمت بحساب عدد بعض العناصر، وطرحت عدد جميع العناصر الأخرى وحصلت على الرقم 0 - فإن العنصر الأصلي الخاص بك لا يمكن أن يكون عنصر أغلبية.هذا إذا كان الأساس لخوارزمية صحيحة:

تحتوي على متغيرين، العداد والعنصر المحتمل.قم بتكرار الدفق، إذا كان العداد هو 0 - قم بالكتابة فوق العنصر المحتمل وتهيئة العداد، إذا كان الرقم هو نفس العنصر المحتمل - قم بزيادة العداد، وإلا قم بتقليله. رمز بايثون:

def majority_element(arr):
    counter, possible_element = 0, None
    for i in arr:
        if counter == 0:
            possible_element, counter = i, 1
        elif i == possible_element:
            counter += 1
        else:
            counter -= 1

    return possible_element

ومن الواضح أن نرى أن الخوارزمية O(n) مع ثابت صغير جدا من قبل O(n) (مثل 3).كما يبدو أن تعقيد الفضاء هو O(1), ، لأنه لم تتم تهيئة سوى ثلاثة متغيرات.تكمن المشكلة في أن أحد هذه المتغيرات عبارة عن عداد يمكن أن يصل إلى مستوى n (عندما يتكون المصفوفة من نفس الأرقام).و لتخزين الرقم n انت تحتاج O(log (n)) فضاء.لذا من الناحية النظرية إنها O(n) وقت و O(log(n)) فضاء. من العملي, ، يمكنك احتواء رقم 2 ^ 128 في الطول وهذا العدد من العناصر في المصفوفة ضخم بشكل لا يمكن تصوره.

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

قناة التاريخ:تم اختراع هذه الخوارزمية في مكان ما في عام 1982 بواسطة Boyer، Moore وتم تسميتها خوارزمية تصويت الأغلبية Boyer-Moore.

Answer 7

ولدي ذكريات هذه الخوارزمية، والتي قد تكون أو لا تتبع قاعدة 2K. قد تحتاج إلى إعادة صياغة مع أكوام وما شابه ذلك لتجنب كسر حدود الذاكرة بسبب المكالمات وظيفة، ولكن هذا قد يكون غير الضرورية لأنها ليس لديها سوى من أي وقت مضى عدد وغاريتمي من مثل هذه الدعوات. على أية حال، لدي ذكريات غامضة من الكلية أو حل عودي إلى هذا الذي تشارك فرق تسد، الكائن السري أنه عند تقسيم المجموعات في نصف واحد على الأقل من نصفين لا يزال لديه أكثر من نصف قيمها متساوية إلى أقصى الحدود . القاعدة الأساسية عند تقسيم هو أن تعود اثنين من كبار القيم مرشح، واحدة منها هي القيمة العليا واحدة منها بعض قيمة أخرى (قد تكون أو لا تكون 2nd مكان). أنسى الخوارزمية نفسها.

Answer 8

وإثبات صحة لبطي-oxa / الجواب جيسون هرنانديز، على افتراض الجواب جيسون هو نفس الجواب بطي-oxa وكلا العمل بالطريقة الخوارزمية وصفت ينبغي العمل:

ونحن نعرف قوة اشتباه تعديل بأنها مساوية لقوة شبهة إذا تم تحديد أعلى قيمة أو قوة -suspicion إذا لم يتم تحديد قيمة أعلى. في كل مرة كنت اختيار العدد المناسب، والمعدلة زيادة قوة اشتباه الحالية 1. في كل مرة كنت اختيار العدد غير صحيح، فإنه إما يسقط بنسبة 1 أو زيادة بنسبة 1، اعتمادا على ما إذا تم تحديد عدد من الخطأ حاليا. لذلك، والحد الأدنى الممكن قوة انتهاء تعديل اشتباه تساوي عدد من [أعلى القيم] - عدد من [قيم أخرى]