الحوسبة وضع الإحصائي

Question

وأنا أحاول حاليا للتحقق ما إذا كان أو لم يكن كذلك، يعطى لم يتم فرزها مجموعة A من طول N وك عدد صحيح، ما إذا كان هناك وجود بعض العناصر التي تحدث مرة ن / ك أو أكثر.

وكان تفكيري لهذه المشكلة لحساب الوضع ثم قارن هذا إلى n / ك. ومع ذلك، وأنا لا أعرف كيف لحساب هذا الوضع بسرعة. بلدي النتيجة النهائية يجب أن تكون ن <م> سجل (ك)، ولكن ليس لدي أي فكرة حقا على كيفية القيام بذلك. أسرع يمكن أن تجد لي كان ن ك ...

Answer 1

استخدم جدول تجزئة لحساب تكرار كل قيمة:

uint[int] counts;
foreach(num; myArray) {
     counts[num]++;
}

int mostFrequent;
uint maxCount = 0;
foreach(num, count; counts) {
    if(count > maxCount) { 
        mostFrequent = num;
        maxCount = count;
    }
}

Answer 2

وتعيين م = ن / ك تقريب. القيام فرز سريع، ولكن تجاهل القوائم الفرعية بطول أقل من متر.

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

وسوف يكون هناك O (سجل (ك)) المستويات لالعودية، ولكل مستوى يأخذ O (ن) وقت.

Answer 3

ومجرد المشي في مجموعة وحفظ التهم في تجزئة / القاموس (وإعادة صحيح مرة واحدة ن وجدت / ك، وإلا كاذبة) سيكون O (ن)

وتحرير، شيء من هذا القبيل:

counts = {}
for n in numbers:
    if ( counts.has_key( n ) ):
        counts[ n ] += 1
    else:
        counts[ n ] = 1
    if ( counts[ n ] >= n / k ):
        return true
return false

Answer 4

وحساب الوضع الإحصائي في F # .NET لمجموعة البيانات (أعداد صحيحة) الذي يحتوي على وضع واحد

let foundX (num: int, dList) = List.filter (fun x -> x = num) dList
let groupNum dList =
    dList
    |> (List.map (fun x -> foundX (x, dList)))
    |> (List.maxBy (fun x -> x.Length))

let Mode (dList: int List) = 
    let x = groupNum dList
    x.Head

//using Mode
let data = [1;1;1;1;1;1;1;1;2;2;3;3;3;1;4;4;4;4;4]
Mode data;;`

Answer 5

وشبة الكود:

 found = false
 value = null
 B = new hashtable
 for (i =0, j = A[i]; i < |A| and !found; ++i, j=A[i])
    if B contains key j
       B[j] = B[j] + 1
       if B[j] > |A|/k
          found = true
          value = j
       endif
    else 
       B[j] = 1
    endif
 end for

وعلى افتراض أن تنفيذ جدول هاش لديه O (1) إدراج / بحث هذا ينبغي أن يكون O (ن)