计数排序

三猫

发布于 2020-11-03 03:03:11

82200

代码可运行

文章被收录于专栏：机器学习养成记机器学习养成记

运行总次数：0

代码可运行

计数排序是典型排序算法之一，今天就来介绍一下计数排序，并通过LeetCode的1365题进行python实例演示。

概念

通常的排序算法是要进行元素之间的比较，而计数排序是记录下每个元素出现的个数，是一种空间换时间的排序方法。适合整数数组排序，并且不同元素个数不宜过多。

算法步骤如下：

扫描nums整个序列，获取最小值和最大值
建立中间数组，长度为 ( max - min + 1)
中间数组中 index 的元素记录的值是nums中某元素出现的次数
遍历中间数组，根据中间数组中的值及index与nums元素取值的对应关系，输出相应个数的元素

其中，第1、2步可以只取最大值并建立长度为max+1的中间数组，即从0开始记录每个数字出现的次数，但当最小值大于0很多时，会造成空间浪费。

（图片来自网络）

python实例展示

题目1365：有多少小于当前数字的数字

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

思路一：计数排序

建立中间数组记录每个值出现的次数，因为最后要输出的是小于某元素的所有数字个数，因此最后一步不是之间遍历输出，而是要把前面的出现次数相加。

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        min_num = min(nums)
        #建立中间数组，记录每个值出现的次数
        #中间数组取值范围为[最小值-1，最大值]
        count_sort = [0]*(max(nums)-min_num+2)
        for i in range(0,len(nums)):
            count_sort[nums[i]-min_num+1]+=1
        #遍历中间数组，输出小于目标元素的元素个数
        result = []
        for i in range(0,len(nums)):
            result.append(sum(count_sort[0:nums[i]-min_num+1]))
        return(result)

思路二：哈希表

首先把nums进行排序，然后记录每个元素第一次出现的位置，那么就可以知道前面有几个数，即题目所求。

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        nums_sort = sorted(nums)
        nums_hash = {}
        for i,item in enumerate(nums_sort):
            if item not in nums_hash:
                nums_hash[item] = i 
        result = []
        for i in range(0,len(nums)):
            result.append(nums_hash[nums[i]])
        return(result)