计数排序

1. 概念定义

计数排序（Counting sort）是一个非基于比较的稳定的线性时间的排序算法，

  1. 非基于比较：之前学的排序都是通过比较数据的大小来实现有序的，比如希尔排序等，而计数排序不用比较数据的大小。

计数排序的名字会让我们想到“计数法”，实际上计数排序的实现就是使用的计数法。（类似哈希表的思想）

工作原理：使用一个额外的数组 cnt，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数，然后根据数组 cnt 来将 A 中的元素排到正确的位置。

具体实现：创建一个足够大的数组 cnt，足够大的意思是 cnt 的下标范围可以包括所有的待排序数据值。然后遍历待排序数据，使用计数法统计每个数据的出现次数。最后遍历 cnt 数组，将每一个值（cnt[i]）不为 0 的下标（i）放入原数组 cnt[i] 次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void countingSort(int *s, int size) {
    int cnt[101];  //因为最大的数据是100，所以数组下标要开到 101，否则会出现数组越界问题
    memset(cnt, 0, sizeof(cnt));  //初始化哈希表
    for(int i = 0; i < size; ++i) {
        cnt[ s[i] ]++;  //将计数的表中对应值所在位置加一
    }
    int sSize = 0;
    for(int i = 0; i < 101; ++i) {  //按顺序取出哈希表中的值
        while(cnt[i]) {
            s[sSize++] = i;  //请自行复习++i和i++的区别
            cnt[i]--;
        }
    }
}

2. 题目练习

  1. 2733. 既不是最小值也不是最大值 - 力扣（LeetCode）
  2. 389. 找不同 - 力扣（LeetCode）

3. 解题报告

2733. 既不是最小值也不是最大值 - 力扣（LeetCode）

题目描述

给你一个整数数组 nums ，数组由 不同正整数 组成，请你找出并返回数组中 任一 既不是 最小值 也不是 最大值 的数字，如果不存在这样的数字，返回 -1 。

返回所选整数。

  1. 1 <= nums.length <= 100
  2. 1 <= nums[i] <= 100
  3. nums 中的所有数字互不相同

解题思路

将原数组排序，判断数组中的数是否与头尾元素相同，否则输出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void countingSort(int *s, int size) {
    int cnt[101];
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < size; ++i) {
        cnt[ s[i] ]++;
    }
    int sSize = 0;
    for(int i = 0; i < 101; ++i) {
        while(cnt[i]) {
            s[sSize++] = i;
            cnt[i]--;
        }
    }
}

int findNonMinOrMax(int* nums, int numsSize){
    countingSort(nums, numsSize);
    for(int i = 0; i < numsSize; ++i) {
        if(nums[i] == nums[0]) continue;
        else if(nums[i] == nums[numsSize-1]) continue;
        else {return nums[i]; break;}
    }
    return -1;
}

389. 找不同 - 力扣（LeetCode）

题目描述

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

  1. 0 <= s.length <= 1000
  2. t.length == s.length + 1
  3. s 和 t 只包含小写字母

解题思路

将字符串排序，逐个比较至两者相同位置的元素不相同，输出t中该元素。

因为是字符串，排序函数需要做一些改动，按字符编码排序，并且别忘了在末尾加上终止符。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void countingSort(char *s) {
    int cnt[256];
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; s[i]; ++i) {
        cnt[ s[i] ]++;
    }
    int sSize = 0;
    for(int i = 0; i < 256; ++i) {
        while(cnt[i]) {
            s[sSize++] = i;
            cnt[i]--;
        }
    }
    s[sSize] = '\0';
}
char findTheDifference(char* s, char* t) {
    countingSort(s);
    countingSort(t);
    int i;
    for(i = 0; s[i]; ++i) {
        if(s[i] != t[i]) return t[i];
    }
    return t[i];
}

题目拓展

  1. 既然能使用计数排序，为什么不直接比较计数情况（通过哈希表）？如何实现？
  2. 既然是增加一个字符，那合并两个字符串后应该会出现有一个字母的数量是奇数。如何利用这一点改进程序？或者是采取一种新方法？（提示：位运算）