根据数组中元素的计数，获取带有元素的数组的频率

Question

这里我有元素的数组。我想从中得到元素数组，根据元素的出现情况降序。

例句:我有["a","b","a","g","a","c","g","g","b","a","b","c","b","c","f","a"]元素数组

预期输出为["a", "b", "c", "g", "f"] --因为我有a's-5, b's-4, c's-3, g's-3, f's-1。(根据重复元素的计数，按降序显示)

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]

我被困在这之后，有人能帮我吗？

Answer 1

如果您正在寻找O(n)时间复杂度算法，您可以使用https://en.wikipedia.org/wiki/Counting_sort (以空间复杂性为代价)：

let arr = ["a","b","a","g","a","c","g","g","b","a","b","c","b","c","f","a"]

让我们构建这个数组的直方图：

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

然后构造一个数组数组，其中元素被放入与计数对应的索引中，减少它们的频率：

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]
}

然后把它压平：

let result = arrayOfArrays.flatMap { $0 }

并检查结果：

print(result)

产生的结果：

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

注意，相同频率的元素在运行之间可能会以不同的顺序出现，因为Dictionary不是一个有序的集合。

Answer 2

你快到了。现在可以根据出现次数的减少对字典进行排序，然后提取键：

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

完整的例子：

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"]

Answer 3

可以通过以下方式对数组进行排序：

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"]