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

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出现两次，5出现三次，6出现四次。并且 [1, 3, 4] 在其中排序。

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

Answer 1

您可以在 O(nlogn) 时间内获得结果，方法是首先创建一个包含每个元素出现次数的 Dictionary (O(n))，然后在 Array(Swift uses Introsort，即 O(nlogn))上调用 sorted 并使用来自之前为排序创建了 Dictionary。数组的元素需要是 Comparable 才能进行排序，并且 Hashable 才能将它们存储在 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})

或者更短，comparing tuples for sorting :

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

生成您提供的示例输出，[1, 3, 4, 2, 2, 5, 5, 5, 6, 6, 6, 6]