J'essaie de trouver l'élément de fréquence le plus élevé dans le donné comme suit.
Tout d'abord, j'essaie de créer un dictionnaire et de compter chaque élément en fonction de la fréquence.
Je ne sais pas comment pour extraire la valeur maximale du dictionnaire construit.
Entrée: [3,2,3]
Résultat: 3
func majorityElement(_ nums1: [Int]) -> Int {
var num1Dict = Dictionary(nums1.map{ ($0, 1) }, uniquingKeysWith : +)
return num1Dict.values.max() // ????
}
3 Réponses :
Vous avez correctement construit num1Dict , qui sera quelque chose comme ceci pour l'entrée [3,2,3] :
func majorityElement(_ nums1: [Int]) -> Int? { // you should probably return an optional here in case nums1 is empty
let num1Dict = Dictionary(nums1.map{ ($0, 1) }, uniquingKeysWith : +)
var currentHigh = Int.min
var mostOccurence: Int?
for kvp in num1Dict {
if kvp.value > currentHigh {
mostOccurence = kvp.key
currentHigh = kvp.value
}
}
return mostOccurence
}
values.max () renverra 2, car sur toutes les valeurs du dictionnaire (1 et 2), 2 est la plus élevée.
Voir votre erreur maintenant?
Vous devez renvoyer la clé associée à la valeur la plus élevée, pas à la valeur la plus élevée.
Une manière très simple est de faire ceci:
[2:1, 3:2]
Existe-t-il un raccourci (fonction d'ordre élevé) pour résoudre ce problème plutôt qu'une combinaison d'utilisation de la boucle for et de la condition if ?
@hotspring Oui, mais utiliser des boucles for est le moyen le plus rapide auquel je puisse penser. Pour un moyen plus lent mais plus court, faites num1Dict.sorted (by: {$ 0.value> $ 1.value}). First! .Key .
vous pouvez également faire num1Dict.filter {$ 0.value == num1Dict.values.max ()} .first! .key
@barbarity Oui, mais notez comment cela a une complexité temporelle de O (n ^ 2).
@Sweeper Je pense que le compilateur est assez intelligent pour savoir que num1Dict.values.max () ne change pas mais dans tous les cas, vous pouvez toujours faire une ligne: let max = num1Dict.values. max () puis num1dict.filter {$ 0.value == max} .first! .key
Le dictionnaire doit encore être répété deux fois, c'est pourquoi j'ai dit que l'utilisation d'une boucle for était le moyen le plus rapide auquel je puisse penser. @barbarie
mais itérer deux fois est 2n qui en termes de calcul est O (n)
La complexité de @barbarity n'est pas la même chose que la vitesse. Je pourrais avoir une opération O (1) constante qui prend 1000 ans. Donc, à moins que filter ne soit plus rapide qu'une boucle for, l'utilisation d'une boucle for est la solution la plus rapide. Vous pouvez essayer de faire quelques repères. Je ne sais pas.
@Sweeper Vous êtes en train de regarder le fait que nums1.map fait un passage complet à travers nums1 , et alloue un tableau de tuples. Vous devez utiliser nums1.lazy.map à la place
@Sweeper Plus, vous lancez une implémentation de max (par :) , et c'est en fait incorrect. Plutôt que de renvoyer nil sur des tableaux vides, il renvoie 0 . Si vous appelez cette méthode et que vous récupérez un 0 , comment savoir si c'est " 0 car il n'y avait aucun élément" et " 0 comme dans l'élément le plus courant est 0 ? " C'est un chèque supplémentaire. C'est un anti-pattern dans Swift. C'est à cela que servent les options.
@Alexander Dans la tentative d'OP, la méthode retourne un Int non optionnel, donc j'ai simplement supposé que le tableau est toujours non vide. Bon point.
@Sweeper C'est votre opportunité de guider OP dans la bonne direction. Renvoyer Int pour quelque chose qui peut avoir un résultat non défini serait tout simplement incorrect.
Vous pouvez utiliser reduction (into :) pour générer un Dictionary avec les éléments et leurs fréquences, puis trier votre tableau en utilisant ces fréquences, puis simplement renvoyer le dernier élément (basé sur l'ordre croissant) du tableau trié.
extension Array where Element: Comparable & Hashable {
func sortByNumberOfOccurences() -> [Element] {
let occurencesDict = self.reduce(into: [Element:Int](), { currentResult, element in
currentResult[element, default: 0] += 1
})
return self.sorted(by: { current, next in occurencesDict[current]! < occurencesDict[next]!})
}
func elementWithHighestFrequency() -> Element? {
return sortByNumberOfOccurences().last
}
}
Clause de non-responsabilité: la méthode sortByNumberOfOccurences est copiée depuis une autre de mes réponses .
Le nom mathématique de ce que vous recherchez (l'élément le plus fréquent d'une collection) est appelé le mode . Il peut y avoir des liens (par exemple, [1, 1, 2, 2, 3, 3] a 3 modes: [1, 2, 3] )
Si vous voulez l'un des modes (sans vous soucier de ceux, en particulier), vous pouvez utiliser Dictionary.max (by :) , que vous pouvez utiliser pour trouver la paire (élément, nombre) avec le nombre le plus élevé (qui est la valeur de dict). Ensuite, vous pouvez obtenir la clé de cette paire, qui sera l'élément mode.
extension Sequence where Element: Hashable {
func countOccurrences() -> [Element: Int] {
return self.reduce(into: [:]) { (occurences, element) in occurences[element, default: 0] += 1}
}
func mode() -> Element? {
return self.countOccurrences()
.max(by: { $0.value < $1.value })?
.key
}
func modes() -> [Element] {
var firstModeNumOccurences: Int? = nil
let modes = countOccurrences()
.sorted { pairA, pairB in pairA.value > pairB.value } // sorting in descending order of num occurences
.lazy
.prefix(while:) { (_, numOccurences) in
if firstModeNumOccurences == nil { firstModeNumOccurences = numOccurences }
return numOccurences == firstModeNumOccurences
}
.map { (element, _) in element }
return Array(modes)
}
}
print([1, 2, 3, 3, 4, 4].mode() as Any) // => 3 or 4, non-deterministic
print([1, 2, 3, 3, 4, 4].modes() as Any) // => [3, 4]
Pourquoi utiliser Any ?
@Connor C'était une chose de débogage temporaire de travailler sur une erreur de type. Fixé maintenant.