根据其频率对数组元素进行排序 [英] Sort array elements based on their frequency

问题描述

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

I need to sort an array of elements based on their frequency, for example:

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次出现3次，6次出现4次.并且[1、3、4]在其中排序.

Description: As 1, 3, 4 occur only once, they are shown at the beginning, 2 occurs two times, 5 three times, 6 four times. And [1, 3, 4] are sorted among them.

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

Expected result: Time complexity should be O(n)

推荐答案

首先创建一个包含每个元素出现次数(O(n))的Dictionary，然后调用Dictionary，即可在O(nlogn)时间内获得结果. sorted上的sorted(

You can achieve the results in O(nlogn) time by first creating a Dictionary containing the number of occurrences for each element (O(n)), then calling sorted on the Array (Swift uses Introsort, which is O(nlogn)) and using the values from the previously created Dictionary for the sorting. The elements of your array need to be Comparable for sorting to work and Hashable to be able to store them in a Dictionary, which provides O(1) element lookup.

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中修改闭包，如下所示:

The above solution preserves the order of elements that occur an equal number of times. If you actually want to sort such elements based on their compared values (which is what your sample output does), you can modify the closure in sorted like below:

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

或更短一些，比较tuples进行排序:

Or even shorter, 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]

which produces the sample output you provided, [1, 3, 4, 2, 2, 5, 5, 5, 6, 6, 6, 6]

这篇关于根据其频率对数组元素进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！