Сортировать элементы массива по частоте

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 (n) примерно следующим образом:

let input = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]

// build the frequency dictionary (easy task)
let frequencies = input.reduce(into: [:]) { $0[$1] = ($0[$1] ?? 0) + 1 }

// allocate a 2-D array of ints, each item in this array will hold the numbers that
// appear I times in the input array
let frequencyTable: [[Int]] = frequencies.reduce(into: Array(repeating: [Int](), count: input.count)) {
    // substracting one as arrays are zero indexed
    // we can't get of of bounds here since the maximum frequency is the 
    // number of elements in the input array
    // Also replicating the numbers by their frequency, to have
    // the same contents as in the input array
    $0[$1.value - 1] += Array(repeating: $1.key, count: $1.value)
}

// lastly, simply flatten the 2-D array to get the output we need
let output = frequencyTable.flatMap { $0 }

print(output)

Пример результата:

[4, 1, 3, 2, 2, 5, 5, 5, 6, 6, 6, 6]

Обратите внимание, что порядок чисел с одинаковой частотой может отличаться в зависимости от того, как работает хэш-функция словаря.

Также мы жертвуем пространство (выделенный 2-D массив) в пользу времени.

Содержимое frequencyTable будет выглядеть примерно так (опять-таки порядок 1, 4, 3 может отличаться):

[[4, 3, 1], [2, 2], [5, 5, 5], [6, 6, 6, 6], [], [], [], [], [], [], [], []]

Answer 2

Вы можете попробовать приведенный ниже код, это сработало правильно.

var inputArray = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]
inputArray.sort()
let freq = inputArray.sorted { f, s in
    inputArray.filter { $0 == f}.count < inputArray.filter { $0 == s}.count
}
print(freq)

Не уверен насчет сложности времени.

Answer 3

Я хочу добавить решение в O (n)

Для сортировки требуется O (nLogn), но этот вопрос также можно решить без использования сортировки с помощью HashMap в Java, поскольку содержит пары, отсортированные в соответствии с ключом.

import java.util.*; 

class Simple 
{ 
    public static void main(String[] arg) 
    {  int inputArray[] = {1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2};
        Map<Integer,Integer> map = new HashMap<Integer,Integer>(); 
        Map<Integer,List<Integer>> map2 = new HashMap<Integer,List<Integer>>();
       for(int i: inputArray)
      {
                  if(map.get(i) == null){
                 map.put(i, 1) ;
                  }
                  else{
                  int a = map.get(i);
                  map.put(i,a+1);
                 }
      }

        // using for-each loop for iteration over Map.entrySet() 
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if(map2.get(entry.getValue()) == null){
                map2.put(entry.getValue(), new ArrayList<Integer>()) ;
            }
            map2.get(entry.getValue()).add(entry.getKey());
        }

        for(Map.Entry<Integer,List<Integer>> entry : map2.entrySet()){
            for(int j=0; j<entry.getValue().size(); j++){
                for(int i=0; i<entry.getKey(); i++){
                System.out.print(entry.getValue().get(j) + " ");
            }
            }

        }    
    }         

}

1. В цикле First for я перебираю массив, сохраняющий пару (значение, вхождение) в map1 (HashMap). Это займет O (n), поскольку операция вставки HashMap (вставка) принимает O (1).
2. В секунду для цикла я выполняю итерацию map1 и вставляю пару (вхождение, список чисел в данном массиве с этим вхождением) в map2 (HashMap2).
3. Теперь в последнем цикле for я перебираю map2 и печатаю все списки один за другим, это означает, что я печатаю каждый элемент данного массива один раз, т.е. я перебираю список каждого ключа и печатаю каждый элемент списка ключ количество раз. Так что это также займет O (n).

подробнее о HashMap Сложность времени: O (n)

Swift Версия вышеуказанного кода

extension Array where Element: Comparable & Hashable {
func sortByNumberOfOccurences() -> [Element] {
    let occurencesDict = self.reduce(into: [Element:Int](), { currentResult, element in
        currentResult[element, default: 0] += 1
    })
    let dict = occurencesDict.sorted(by: {$0.0 < $1.0})
    var dictioanary = [Int:Array]()
    for (element,occurence) in dict {
        if dictioanary[occurence] == nil
        {
            dictioanary[occurence] = Array()
        }
        dictioanary[occurence]?.append(element)
    }


    var resultArray = Array()
    let finalDict = dictioanary.sorted(by: {$0.0  < $1.0})
    for (frequency,allValuesOccuringWithThisFrequncy) in finalDict {
       for i in allValuesOccuringWithThisFrequncy
       {
        var j = 0
        while(j < frequency)
        {
            resultArray.append(i)
            j = j + 1
        }
       }
    }
    print(resultArray)
    return resultArray
}

}

Сложность времени в Swift O (nLogn)

Answer 4

var inputArray = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]
var map:[Int: Int] = [:]
for element in inputArray {
    let count = map[element]
    if count == nil {
        map[element] = 1
    } else {
        map[element] = count! + 1
    }
}
var keysArray = map.keys
let sortedKeys = keysArray.sorted { (number1, number2) -> Bool in
    if map[number1]! == map[number2]! {
        return number1 < number2
    } else {
        return map[number1]! < map[number2]!
    }
}
var finalArray: [Int] = []
for element in sortedKeys {
    for _ in 1...map[element]! {
        finalArray.append(element)
    }
}
print(finalArray)

Сложность времени: O (nlogn)

Answer 5

Вы можете достичь результатов за O(nlogn) время, сначала создав Dictionary, содержащее количество вхождений для каждого элемента (O(n)), затем вызвав sorted для Array ( Swift использует Introsort , который O(nlogn)) и использует значения из ранее созданного 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})

Или даже короче, , сравнивая tuples для сортировки :

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

, который дает предоставленный вами образец выборки, [1, 3, 4, 2, 2, 5, 5, 5, 6, 6, 6, 6]

Answer 6

Нет способа сортировки с O (n) сложностью по времени. Посмотрите на сложность наихудшего случая для популярных алгоритмов в Википедии.

Лучшая временная сложность в худшем случае - O (nlogn). Вот как мы можем решить это с O (nlogn) временной сложностью:

    let array = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]

    extension Array where Element: Comparable & Hashable {
        func countableSorted() -> [Element] {
            var counts = [Element: Int]()
            // O(n)
            for element in self {
                counts[element] = (counts[element] ?? 0) + 1
            }

            // I think that standart method uses O(nlogn) time complexity.
            // O(nlogn) + O(n) approximately equal to O(nlogn).
            let sorted = counts.sorted { item1, item2 -> Bool in
                if item2.value > item1.value {
                    return true
                }

                if item2.value == item1.value {
                    return item2.key > item1.key
                }

                return false
            }

            var result = [Element]()
            // O(n)
            for item in sorted {
                let items = Array(repeating: item.key, count: item.value)
                result.append(contentsOf: items)
            }

            // Total time complexity for worst case scenario is O(nlogn)

            return result
        }
    }

    print(array.countableSorted())

    // Output: [1, 3, 4, 2, 2, 5, 5, 5, 6, 6, 6, 6]

Answer 7

Вы можете попробовать

let dd = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]
let res = dd.sorted { f, s in
    dd.filter { $0 == f }.count <   dd.filter { $0 == s }.count 
} 
print(res) // [1, 4, 3, 2, 2, 5, 5, 5, 6, 6, 6, 6]

Answer 8

Попробуйте это решение.Это сработало для меня как шарм:)

func numberOfOccurences(in array: [Int], of element: Int) -> Int {
    let object = NSCountedSet(array: array)
    return object.count(for: element)
}

var inputArray = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]

var uniqueElements = Array(Set(inputArray))

var otherArray: [Int] = []

var duplicateElements = uniqueElements.filter { (element) -> Bool in
    return (inputArray.contains(element) && numberOfOccurences(in: inputArray, of: element) > 1)
}

uniqueElements = uniqueElements.filter({ !duplicateElements.contains($0) }).sorted()

for item in duplicateElements {
    let occurences = numberOfOccurences(in: inputArray, of: item)
    for _ in 0...occurences - 1 {
        otherArray.append(item)
    }
}

otherArray = otherArray.sorted()

duplicateElements.removeAll()

let mergedArray = uniqueElements + otherArray

print(mergedArray)