Элемент с самой высокой частотой в словаре

Question

Я пытаюсь найти элемент самой высокой частоты в приведенном ниже.

Сначала я пытаюсь построить словарь и посчитать каждый элемент на основе частоты.

Я застрял, как извлечь максимальное значение из составленного словаря.

Ввод: [3,2,3]

Вывод: 3

func majorityElement(_ nums1: [Int]) -> Int {

    var num1Dict = Dictionary(nums1.map{ ($0, 1) }, uniquingKeysWith : +)
    return num1Dict.values.max() // ????

}

Answer 1

Вы можете использовать reduce(into:) для генерации Dictionary с элементами и их частотами, затем отсортировать массив по этим частотам, а затем просто вернуть последний элемент (в порядке возрастания) отсортированного массива.

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

    func elementWithHighestFrequency() -> Element? {
        return sortByNumberOfOccurences().last
    }
}

Отказ от ответственности: метод sortByNumberOfOccurences скопирован из другого моего ответа .

Answer 2

Математическое название того, что вы ищете (самый частый элемент в коллекции), называется mode .Могут быть связи (например, [1, 1, 2, 2, 3, 3] имеет 3 режима: [1, 2, 3])

Если вы хотите какой-либо из режимов (не обращая внимания, какие именно), вы можете использовать Dictionary.max(by:), который можно использовать для поиска пары (элемент, количество) с наибольшим количеством (которое является значением dict).Затем вы можете получить ключ этой пары, который будет элементом mode.

extension Sequence where Element: Hashable {
    func countOccurrences() -> [Element: Int] {
        return self.reduce(into: [:]) { (occurences, element) in occurences[element, default: 0] += 1}
    }

    func mode() -> Element? {
        return self.countOccurrences()
            .max(by: { $0.value < $1.value })?
            .key
    }

    func modes() -> [Element] {
        var firstModeNumOccurences: Int? = nil
        let modes = countOccurrences()
            .sorted { pairA, pairB in pairA.value > pairB.value } // sorting in descending order of num occurences
            .lazy
            .prefix(while:) { (_, numOccurences) in
                if firstModeNumOccurences == nil { firstModeNumOccurences = numOccurences }
                return numOccurences == firstModeNumOccurences
            }
            .map { (element, _) in element }

        return Array(modes)
    }
}

print([1, 2, 3, 3, 4, 4].mode() as Any) // => 3 or 4, non-deterministic
print([1, 2, 3, 3, 4, 4].modes() as Any) // => [3, 4]

Answer 3

Вы правильно построили num1Dict, что будет примерно так для ввода [3,2,3]:

[2:1, 3:2]

values.max() вернет 2, потому что из всех значений в словаре (1 и 2), 2 - самое высокое.

Вы видите свою ошибку сейчас?

Вам необходимо вернуть ключ, связанный с наибольшим значением, а не с самым высоким значением.

Один очень простой способ сделать это:

func majorityElement(_ nums1: [Int]) -> Int? { // you should probably return an optional here in case nums1 is empty

    let num1Dict = Dictionary(nums1.map{ ($0, 1) }, uniquingKeysWith : +)
    var currentHigh = Int.min
    var mostOccurence: Int?
    for kvp in num1Dict {
        if kvp.value > currentHigh {
            mostOccurence = kvp.key
            currentHigh = kvp.value
        }
    }
    return mostOccurence

}