Задача: Сортировка массива

Условие: дается массив целых чисел nums, отсортируйте массив в порядке возрастания и верните его.

Вы должны решить проблему без использования каких-либо встроенных функций в O(nlog(n)) временной сложности и с наименьшей возможной пространственной сложностью.

Пример:

Ввод: nums = [5,2,3,1]

Вывод: [1,2,3,5] 

Ввод: nums = [5,1,1,2,0,0]

Вывод: [0,0,1,1,2,5]

Решение:

Python

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        
        """
        This is a sorting done in linear time, a good idea if the range of numbers are small
        O(n) time for creating the freq_dict and calculating min and max
        O(R) time for the next for loop where R is the range of the list
        Total time: O(n+R) and total space: O(n) for creating the freq_dict and the ans array
        """
        
        freq_dict = {}
        for i in nums:
            if i in freq_dict:
                freq_dict[i] = freq_dict[i] + 1
            else:
                freq_dict[i] = 1
                
        min_num, max_num = min(nums),max(nums)
        ans = []
        for num in range(min_num, max_num + 1):
            if num in freq_dict:
                ans.extend([num]*freq_dict[num])
        return ans