3
votes

Obtenez la fréquence du tableau avec les éléments, en fonction du nombre d'éléments dans le tableau

Ici, j'ai le tableau des éléments. Je voudrais obtenir le tableau des éléments à partir de cela, dans l'ordre décroissant en fonction de l'occurrence des éléments.

Ex: J'ai un tableau d'éléments ["a", "b", "a", "g", "a", "c", "g", "g", "b", "a", "b", "c", "b", "c", "f", "a"]

Le résultat attendu est ["a", "b", "c", "g", "f"] - Parce que j'ai a's-5, b's-4, c's-3, g's-3, f's-1 . (Affichage par ordre décroissant, basé sur le nombre d'éléments répétés)

let x = ["1","2","3","1","1","2","3","3","3","3"]
let cnts = x.reduce(into: [:]) {
    counts, word in
    counts[word, default: 0] += 1
}
print(cnts) //["a": 5, "c": 3, "f": 1, "g": 3, "b": 4]

Je suis bloqué après cela, quelqu'un peut-il m'aider?

swift arrays

2 commentaires

Il y a des incohérences. Dans le premier tableau, "f" apparaît une seule fois, pas quatre fois. La sortie ["a": 5, "c": 3, "f": 1, "g": 3, "b": 4] ne correspond pas au let défini précédemment x = ["1", "2", "3", "1", "1", "2", "3", "3", "3", "3"]

Lorsque les éléments ont le même nombre d'occurrences, l'ordre de sortie attendu de ces éléments a-t-il de l'importance? c'est-à-dire: ["g", "f", "f", "g"] => ["f", "g"] ou [" g "," f "] ? Si cela a de l'importance, en fonction de l'ordre d'apparition dans l'entrée? Par ordre alphabétique?

3 Réponses :

2
votes

Vous y êtes presque. Vous pouvez maintenant trier le dictionnaire en fonction d'un nombre décroissant d'occurrences, puis extraire les clés:

let x = ["a","b","a","g","a","c","g","g","b","a","b","c","b","c","f","a"]
// 5 x "a", 4 x "b", 3 x "c", 1 x "f", 3 x "g"

let cnts = x.reduce(into: [:]) {
    counts, word in
    counts[word, default: 0] += 1
}
print(cnts) // ["g": 3, "c": 3, "b": 4, "f": 1, "a": 5]

let result = cnts.sorted(by: { $0.value > $1.value }).map { $0.key }
print(result) // ["a", "b", "g", "c", "f"]

L'exemple complet:

let result = cnts.sorted(by: { $0.value > $1.value }).map { $0.key }

2 commentaires

@Len_X: Merci pour la suggestion de modification. Mais la sortie affichée est correcte. "f" n'apparaît qu'une seule fois dans le tableau donné. "c" et "g" se produisent tous les deux trois fois, donc l'ordre entre ceux-ci n'est pas spécifié.

Addendum: Dans Swift <5, le tri est le O (nlogn) meilleur cas, O (n ^ 2) le pire des cas. Dans Swift 5, avec TimSort, le meilleur des cas serait O (n) , O (nlogn) le pire des cas.

1
votes

Vous pouvez trier le tableau par:

let arr = ["a","b","a","g","a","c","g","g","b","a","b","c","b","c","f","a"]
var counts: [String: Int] = [:]

arr.forEach { counts[$0, default: 0] += 1 }

print(counts)
//["a": 5, "c": 3, "g": 3, "f": 1, "b": 4]
let sortedByValueDictionary = counts.sorted(by :{ $0.1 < $1.1 }).map { $0.key }
print(sortedByValueDictionary)
//["a", "b", "g", "c", "f"]

3 commentaires

Vous triez le dictionnaire en fonction des touches , pas en fonction des fréquences. La sortie n'est pas correcte car "g" apparaît plus souvent que "f".

Avez-vous exécuté votre code? Maintenant, la sortie est ["f", "g", "c", "b", "a"] , c'est-à-dire le contraire de l'ordre décroissant demandé en fonction de l'occurrence des éléments. "

Modifiez l'expression de sortedByValueDictionary en count.sorted (par: {$ 0,1> $ 1,1}). Map {$ 0.key}

1
votes

Si vous recherchez un algorithme de complexité temporelle O (n) , vous pouvez utiliser Tri par comptage (au prix de la complexité spatiale):

print(result)

Construisons l'histogramme de ce tableau:

XXX

Puis construis un tableau de tableaux où les éléments sont mis dans l'index qui correspond au décompte hache leur fréquence:

let result = arrayOfArrays.flatMap { $0 }

Et puis aplatir:

var acc = Array(repeating: [String](), count: arr.count)
//Array indexes are 0-based
let lastIndex = arr.count - 2

let arrayOfArrays: [[String]] = histogram
    .reduce(into: acc) { accumulator, entry in
        accumulator[lastIndex - entry.value] += [entry.key]
}

Et vérifier le résultat:

let histogram = arr.reduce(into: [:]) {
    $0[$1, default: 0] += 1
}

qui donne:

["a", "b", "c", "g", "f"]

Notez que les éléments avec la même fréquence peuvent apparaître dans des ordres différents entre les exécutions car un Dictionnaire n'est pas une collection ordonnée.

0 commentaires