Trier les éléments du tableau en fonction de leur fréquence

var inputArray = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]
var map:[Int: Int] = [:]
for element in inputArray {
    let count = map[element]
    if count == nil {
        map[element] = 1
    } else {
        map[element] = count! + 1
    }
}
var keysArray = map.keys
let sortedKeys = keysArray.sorted { (number1, number2) -> Bool in
    if map[number1]! == map[number2]! {
        return number1 < number2
    } else {
        return map[number1]! < map[number2]!
    }
}
var finalArray: [Int] = []
for element in sortedKeys {
    for _ in 1...map[element]! {
        finalArray.append(element)
    }
}
print(finalArray)
Time Complexity: O(nlogn)

Vous pouvez essayer le code ci-dessous, cela a fonctionné correctement.

var inputArray = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]
inputArray.sort()
let freq = inputArray.sorted { f, s in
    inputArray.filter { $0 == f}.count < inputArray.filter { $0 == s}.count
}
print(freq)

Je ne suis pas sûr de la complexité temporelle.

Je souhaite ajouter une solution en O (n)

Le tri prend O (nLogn) mais cette question peut également être résolue sans utiliser le tri à l'aide de HashMap en Java car il contient les paires triées selon la clé.

extension Array where Element: Comparable & Hashable {
func sortByNumberOfOccurences() -> [Element] {
    let occurencesDict = self.reduce(into: [Element:Int](), { currentResult, element in
        currentResult[element, default: 0] += 1
    })
    let dict = occurencesDict.sorted(by: {$0.0 < $1.0})
    var dictioanary = [Int:Array]()
    for (element,occurence) in dict {
        if dictioanary[occurence] == nil
        {
            dictioanary[occurence] = Array()
        }
        dictioanary[occurence]?.append(element)
    }


    var resultArray = Array()
    let finalDict = dictioanary.sorted(by: {$0.0  < $1.0})
    for (frequency,allValuesOccuringWithThisFrequncy) in finalDict {
       for i in allValuesOccuringWithThisFrequncy
       {
        var j = 0
        while(j < frequency)
        {
            resultArray.append(i)
            j = j + 1
        }
       }
    }
    print(resultArray)
    return resultArray
}

1. Dans la boucle First for, je suis en train d'itérer à travers une paire de sauvegarde de tableau de (valeur, occurrence) dans map1 (HashMap). Cela prendra O (n) comme l'opération put (insertion) HashMap prend O (1).
2. Dans la deuxième boucle for, j'itère map1 et j'insère une paire de (occurrence, liste de nombres dans le tableau donné avec cette occurrence) dans map2 (HashMap2).
3. Maintenant, dans la dernière boucle for, j'itère dans map2 et j'imprime toutes les listes une par une, cela signifie que j'imprime chaque élément du tableau donné une fois, c'est-à-dire que je suis en train d'itérer la liste de chaque clé et d'imprimer chaque élément de la liste key nombre de fois. Donc, cela prendrait également O (n).

en savoir plus sur HashMap Complexité temporelle: O (n)

Version Swift du code ci-dessus

import java.util.*; 

class Simple 
{ 
    public static void main(String[] arg) 
    {  int inputArray[] = {1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2};
        Map<Integer,Integer> map = new HashMap<Integer,Integer>(); 
        Map<Integer,List<Integer>> map2 = new HashMap<Integer,List<Integer>>();
       for(int i: inputArray)
      {
                  if(map.get(i) == null){
                 map.put(i, 1) ;
                  }
                  else{
                  int a = map.get(i);
                  map.put(i,a+1);
                 }
      }

        // using for-each loop for iteration over Map.entrySet() 
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if(map2.get(entry.getValue()) == null){
                map2.put(entry.getValue(), new ArrayList<Integer>()) ;
            }
            map2.get(entry.getValue()).add(entry.getKey());
        }

        for(Map.Entry<Integer,List<Integer>> entry : map2.entrySet()){
            for(int j=0; j<entry.getValue().size(); j++){
                for(int i=0; i<entry.getKey(); i++){
                System.out.print(entry.getValue().get(j) + " ");
            }
            }

        }    
    }         

}

}

Complexité temporelle dans Swift O (nLogn)

Je pense que ce type de tri peut être réalisé en O (n), avec quelque chose comme ce qui suit:

[[4, 3, 1], [2, 2], [5, 5, 5], [6, 6, 6, 6], [], [], [], [], [], [], [], []]

Exemple de résultat:

[4, 1, 3, 2, 2, 5, 5, 5, 6, 6, 6, 6]

Notez que l'ordre des nombres avec la même fréquence peut différer en fonction du fonctionnement de la fonction de hachage du dictionnaire.

Nous sacrifions également l'espace (tableau 2-D alloué) au profit du temps. p >

Le contenu de frequencyTable ressemblera à ceci (encore une fois, l'ordre de 1, 4, 3 peut différer):

let input = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]

// build the frequency dictionary (easy task)
let frequencies = input.reduce(into: [:]) { $0[$1] = ($0[$1] ?? 0) + 1 }

// allocate a 2-D array of ints, each item in this array will hold the numbers that
// appear I times in the input array
let frequencyTable: [[Int]] = frequencies.reduce(into: Array(repeating: [Int](), count: input.count)) {
    // substracting one as arrays are zero indexed
    // we can't get of of bounds here since the maximum frequency is the 
    // number of elements in the input array
    // Also replicating the numbers by their frequency, to have
    // the same contents as in the input array
    $0[$1.value - 1] += Array(repeating: $1.key, count: $1.value)
}

// lastly, simply flatten the 2-D array to get the output we need
let output = frequencyTable.flatMap { $0 }

print(output)