Counting Sort算法介绍

本文主要介绍Counting Sort（计数排序）算法的相关知识，同时通过示例代码介绍这种算法的常见用法。

1 概述

Counting sort是一种基于给定范围数值的排序技术。该算法首先计算给定输入序列（如数组）中每个对象的数量，同时将对象数量值存储在临时数组的对应索引处，最后通过一系列算术操作计算出每个对象在输出序列中的位置。

2 特点

Counting sort算法的特点如下：

• counting sort会对输入序列进行假设。例如，假设输入序列中的数值范围为0到10，或10到99，等等。某些场景下，counting sort也会假设输入数据为所有实数；
• counting sort不是一个基于比较的排序算法，它将输入数据散列（hash）到一个临时计数数组中，然后再进行排序；
• 由于counting sort需要使用临时数组，因此它不是一个原地算法（In-place algorithm）。

一般来说，输入序列取值范围在1到10K之间，都可以考虑使用counting sort算法。

3 常见用法

虽然counting sort是一种排序算法，但是我们可以利用该算法的核心思想来解决一些其他问题。

3.1 存储输入数据中每个元素的出现次数

假设有一组取值范围为0到9的数字，现要求存储每个数字的出现次数。

对于这个问题，就可以使用counting sort思想了。

例如，假设输入序列为：{1, 4, 1, 2, 7, 5, 2}，则此问题的解答步骤如下：

1. 新建一个长度为10（因为输入数据的取值范围为0到9）的临时数组，如下图：

2. 统计输入序列的中每个元素的出现次数。元素每出现一次，就根据该元素的值匹配临时数组中对应的索引，然后将该索引对应的数组值（次数值）加1，如下图：

3. 遍历过输入数据后，就可以得到的存储输入数据元素出现次数的临时数组了，如下图：

至此，本问题解答完成。

3.2 Count Number of Pairs With Absolute Difference K

下面通过LeetCode中的一道题，来介绍couting sort的应用。

3.2.1 题目描述

2006. Count Number of Pairs With Absolute Difference K

Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.

The value of |x| is defined as:

x if x >= 0.
-x if x < 0.

Example 1:

Input: nums = [1,2,2,1], k = 1
Output: 4
Explanation: The pairs with an absolute difference of 1 are:
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]

Example 2:

Input: nums = [1,3], k = 3
Output: 0
Explanation: There are no pairs with an absolute difference of 3.

Example 3:

Input: nums = [3,2,1,5,4], k = 2
Output: 3
Explanation: The pairs with an absolute difference of 2 are:
- [3,2,1,5,4]
- [3,2,1,5,4]
- [3,2,1,5,4]

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100
• 1 <= k <= 99

3.2.2 解题思路

由于输入数据是一个整型数组，同时存在“1 <= nums[i] <= 100”这条约束，因此可以考虑使用counting sort方法来解决。

先使用counting sort方法来生成一个存储输入数据中每个元素出现次数的临时数组，再根据题目要求，找出临时数组中间距为k的数字对数，该数字对数即为此题答案。

解决方案代码如下：

class Solution {
public:
    int countKDifference(vector<int>& nums, int k) {
        int count = 0;
        vector<int> v(101);
        for (auto i:nums) {
            ++v[i];
        }
        // as 1 <= nums[i]
        for (int i = 1; i + k < v.size(); i++) {
            count += v[i] * v[i + k];
        }

        return count;
    }
};