Häufigstes Element in einem Array

Question

Gegeben sind alle Zahlen im Bereich von 0 bis n-1, wobei n die Länge des Arrays ist.

Wie löst man das in linearer Zeit und konstantem Raum?

Answer 1

Sie können gegebenen Array als Zähler für Zahlen wiederverwenden. Iterieren Sie einfach das Array und inkrementieren Sie den entsprechenden Zähler. Der einzige Trick ist, jedes Mal um n zu inkrementieren, nicht von einer:

for (int i = 0; i < n; ++i) { 
    arr[arr[i]%n] += n; 
} 

Nach diesem Schleifenelement arr [i] verändert wird, um arr [i] + n * count [i], wobei arr [i ] < n. Auf diese Weise ist das häufigste Element dasjenige mit dem größten Wert. Um den ursprünglichen Wert wiederherzustellen, nehmen Sie einfach arr [i]% n.

Answer 2

Hier ist eine Funktion, um dies zu erreichen. Aber es ist nicht O (n), wie du es verlangst, es ist O (n^2). Hoffe, diese Hilfe

function getPopularElement(array) { 
    var count = 1, tempCount; 
    var popular = array[0]; 
    var temp = 0; 

    for (var i = 0; i < (array.length - 1); i++) { 
    temp = array[i]; 
    tempCount = 0; 

    for (var j = 1; j < array.length; j++) { 
     if (temp == array[j]) { 
     tempCount++; 
     } 
    } 

    if (tempCount > count) { 
     popular = temp; 
     count = tempCount; 
    } 
    } 

    return popular; 
} 

Answer 3

Heller's Lösung ist eigentlich ähnlich: Die Idee ist, durch das Array zu gehen und für jedes Element einen Zähler an der Position dieser Zahl im Array zu erhöhen. Im Allgemeinen gibt es ein anderes Element an dieser Position (wo Heller die Information durch Zählen in Schrittgrößen von n hält) aber können wir diese Elemente rekursiv und in-Place auflösen. Dies ist ein linearer Prozess, der höchstens einmal pro Element ausgeführt wird, da es keine Ketten mehr geben kann (versuchen, die Anzahl an einer Position zu erhöhen, ein neues Element zu finden) als die Länge des gesamten Arrays (dh ein einzelner Permutationszyklus) und einmal Ein Element wird verarbeitet, es kann in der Hauptschleife übersprungen werden, wodurch es insgesamt O(n) wird. Der Trick ist, um den Zähler zu verringern:

//input: arr 
//output: most frequent element, number of occurrences 
n <- arr.length 
for i = 0..n-1 
    val <- arr[i] 
    if val < 0 
     // this element has already been processed 
     continue 
    // set counter at i to zero (-1) 
    arr[i] <- -1 
    // resolve the chain 
    do 
     idx <- val 
     val <- arr[idx] 
     if val < 0 
      // arrived at a counter, end of chain 
      // increase the counter by one (-1) 
      arr[idx] <- arr[idx] - 1 
      break 
     } 
     // otherwise continue the chain with val 
     // and initialise the counter at idx to one (-2) 
     arr[idx] <- -2 

// find the most common element 
idx <- 0 
for i = 1..n-1 
    // smaller value means larger counter 
    if arr[i] < arr[idx] 
     idx <- i 

// [the most frequent element, number of occurrences] 
output [idx, -(arr[idx] + 1)] // arr[i] = -1 - #occurrences 

Diese Lösung auch schön mit sehr großen Arrays beschäftigt, wo die größten möglichen Gegen in Heller-Lösung (n*n-1) die zugrunde liegende ganze Zahl überlaufen (für 32-Bit-Integer, die Arrays länger ist als 65535 Elemente!)