LeetCode 计数排序 题解题目描述实现计数排序算法对一个整数数组进行排序。示例 1输入nums [5,2,3,1] 输出[1,2,3,5]示例 2输入nums [5,1,1,2,0,0] 输出[0,0,1,1,2,5]解题思路方法计数排序思路计数排序是一种非比较排序算法它的工作原理是统计数组中每个元素出现的次数然后根据统计结果重建排序后的数组。计数排序的过程是首先找出数组中的最大值和最小值然后创建一个长度为最大值减最小值加 1 的计数数组统计每个元素出现的次数最后根据计数数组重建排序后的数组。复杂度分析时间复杂度O(n k)其中 n 是数组的长度k 是数组中元素的范围最大值减最小值加 1。空间复杂度O(k)需要使用计数数组来存储每个元素出现的次数。代码实现方法计数排序def counting_sort(nums): # 处理边界情况 if not nums: return nums # 找出数组中的最大值和最小值 min_val min(nums) max_val max(nums) # 计算计数数组的长度 count_len max_val - min_val 1 # 初始化计数数组 count [0] * count_len # 统计每个元素出现的次数 for num in nums: count[num - min_val] 1 # 重建排序后的数组 sorted_nums [] for i in range(count_len): # 将每个元素按照出现次数添加到排序后的数组中 sorted_nums.extend([i min_val] * count[i]) return sorted_nums # 测试 nums1 [5,2,3,1] print(counting_sort(nums1)) # 输出[1,2,3,5] nums2 [5,1,1,2,0,0] print(counting_sort(nums2)) # 输出[0,0,1,1,2,5]测试用例测试用例 1输入nums [5,2,3,1]输出[1,2,3,5]测试用例 2输入nums [5,1,1,2,0,0]输出[0,0,1,1,2,5]总结本题是排序算法的经典问题主要考察对计数排序算法的理解和实现。计数排序是一种非比较排序算法它通过统计数组中每个元素出现的次数然后根据统计结果重建排序后的数组。计数排序的核心思想是找出数组中的最大值和最小值创建一个计数数组来统计每个元素出现的次数然后根据计数数组重建排序后的数组。这种方法的时间复杂度为 O(n k)其中 k 是数组中元素的范围适用于元素范围较小的情况。掌握计数排序的原理对于理解非比较排序算法和算法设计思想非常重要。