Here I have the array of the elements. I would like get the array of elements from that, descending order based on the occurrence of the elements.
Ex: I Have array of elements ["a","b","a","g","a","c","g","g","b","a","b","c","b","c","f","a"]
Expected Output is ["a", "b", "c", "g", "f"]
- Because I have a's-5, b's-4, c's-3, g's-3, f's-1. (Showing in descending order, based on the count of repeated elements)
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]
I am stuck after this, can anyone help me?
You are almost there. You can now sort the dictionary according to decreasing number of occurrences, and then extract the keys:
let result = cnts.sorted(by: { $0.value > $1.value }).map { $0.key }
The full example:
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"]
You can sort the array by:
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"]
If you're looking for a O(n) time complexity algorithm, you could use Counting sort (at the price of space complexity) :
let arr = ["a","b","a","g","a","c","g","g","b","a","b","c","b","c","f","a"]
Let's build the histogram of this array :
let histogram = arr.reduce(into: [:]) {
$0[$1, default: 0] += 1
}
Then construct an array of arrays where the elements are put in the index that corresponds to the count mince their frequency :
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]
}
And then flatten it :
let result = arrayOfArrays.flatMap { $0 }
And check the result :
print(result)
which yields :
["a", "b", "c", "g", "f"]
Note that elements with the same frequency may appear in different orders between runs since a Dictionary isn't an ordered collection.