根据频率对数组元素进行排序

Question

我需要根据频率对元素数组进行排序,例如:

Input array: [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]
Expected output: [1, 3, 4, 2, 2, 5, 5, 5, 6, 6, 6, 6]

我试过下面的代码:

var set: NSCountedSet = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]

var dictionary = [Int: Int]()
set.forEach { (item) in
    dictionary[item as! Int] = set.count(for: item)
}
dictionary.keys.sorted()
print(dictionary)

说明:由于1,3,4只出现一次,它们在开头显示,2次出现2次,5次出现3次,6次出现4次.并且[1,3,4]在它们之间进行排序.

预期结果:时间复杂度应为O(n)

Answer 1

可以实现在结果O(nlogn)通过首先创建一个时间Dictionary出现的含有数为每个元素(O(n)),则调用sorted在Array(夫特使用内省排序,这是O(nlogn)从先前创建的),并使用这些值Dictionary的排序.数组的元素需要Comparable进行排序才能工作,并Hashable能够将它们存储在a中Dictionary,从而提供O(1)元素查找.

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

[1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2].sortByNumberOfOccurences() // [1, 4, 3, 2, 2, 5, 5, 5, 6, 6, 6, 6]

上述解决方案保留了发生相同次数的元素的顺序.如果你真的想根据它们的比较值(这是你的示例输出所做的那样)对这些元素进行排序,你可以修改闭包,sorted如下所示:

return self.sorted(by: {occurencesDict[$0]! <= occurencesDict[$1]! && $0 < $1})

甚至更短,比较tuples排序:

return self.sorted(by: {(occurencesDict[$0]!,$0) < (occurencesDict[$1]!,$1)})

产生你提供的样本输出, [1, 3, 4, 2, 2, 5, 5, 5, 6, 6, 6, 6]