算法基础算法

微扰法 | 对频数进行计数排序

字数统计: 1.3k字   |   阅读时长: 5分
, , ,

摘要: 对频数进行计数排序

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在排序问题中，如果元素的取值范围不大，可以通过计数的方式排序，突破基于比较的排序算法的 $\Omega(N\log N)$ 的理论下界。通过计数进行排序的主流算法主要有三个：计数排序，基数排序，桶排序。

本文我们要解决的问题，最后是要对频数进行排序，而频数最大不会超过数组的长度，因此自然可以计数排序，由于计算频数本身就是计数排序的一步，对频数进行计数排序，粗略地就可以理解为做了两层计数。

本题我们在频数上做了计数排序，这种对频数而不是对数组对象本身施加算法或数据结构，是个很常见的操作，应用最广泛的是频数前缀和、权值线段树等。

题目

给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。

返回 至少 能删除数组中的一半整数的整数集合的最小大小。

示例 1：
输入：arr = [3,3,3,3,5,5,5,2,2,7]
输出：2
解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。

示例 2：
输入：arr = [7,7,7,7,7,7]
输出：1
解释：我们只能选择集合 {7}，结果数组为空。

提示：

1
2
3
1 <= arr.length <= 1e5
arr.length 为偶数
1 <= arr[i] <= 1e5

题解

算法：贪心、计数排序

假设数组 $A$ 的长度为 $n$，$n$ 为偶数。数组中的元素集合为 $S$，共有 $k = |S|$ 个元素，各个元素 $s_{i}$ 的个数为 $n_{i}$，$i=1,2,\cdots,k$，且有 $\sum\limits_{i=1}\limits^{k}n_{i} = n$。

我们要选出 $\{1,2,\cdots,k\}$ 的一个子集 $I$，将子集中的元素删除，那么被删除的元素集为 $\{s_{i}: i \in I\}$，共删除的元素数为 $\sum\limits_{i \in I}n_{i}$。

要求删除的元素数至少为 $\frac{n}{2}$，同时使得 $|I|$ 尽量小。因此我们的问题是：

注意到这里我们的结果只与选入子集的各个元素的频数 $n_{i}$ 有关，而与具体的元素 $s_{i}$ 无关，因此我们首先需要预处理出各个元素的频数 $n_{i}$。

在有了 $n_{i}$ 之后，凭感觉猜想出以下结论。

引理

最优解一定出现在最大的若干个 $n_{i}$ 对应的指标集作为被删除子集 $I$ 的情况。

证明（微扰法）

记当前的被删子集 $I$ 由最大的若干个 $n_{i}$ 对应的指标组成，首先 $I$ 足够大，即满足 $\sum\limits_{i \in I}n_{i} \geq \frac{n}{2}$，此时 $I$ 是一个可行解。

进一步假设 $I$ 中也无法删除任何一个元素，即 $\forall j \in I$，$\sum\limits_{i \in I\setminus \{j\}}n_{i} < \frac{n}{2}$。记此时 $|I| = a$。那么此时如果想让 $I$ 发生合法的改变，只能是从 $I$ 和 $\overline{I}$ 中交换一部分元素。

而由于 $I$ 中是 $n_{i}$ 最大的 $a$ 个指标，那么从 $I$ 中不论换出去哪些指标，从 $\overline{I}$ 中换进来的指标个数不可能更少，还有可能更多。也就是 $|I| = a$ 无法变得更小，甚至可能变大，因此 $a$ 是最优解。

$\Box$

综上，在预处理出 $n_{i}$ 之后，可以进行贪心算法，即将 $k$ 个数组元素对应的频数 $n_{i}$，$i=1,2,\cdots,k$ 排序，然后从大到小往 $I$ 里添加，直至 $I$ 中各指标对应的频数的和不小于 $\frac{n}{2}$ 了，就停止，返回此时的 $I$。

而由于频数 $n_{i}$ 最大不会超过数组的长度 $n$，因此适用计数排序，也就是对 $n_{i}$ 的集合进行计数排序，而 $n_{i}$ 也是计数得来的，于是整体看相当于做了两层计数。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import Counter

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        # 算频数
        freqs = Counter(arr)

        # 对 cnts 中的频数字段计数排序
        n = len(arr)
        freq_cnts = [0] * (n + 1)
        for x, freq in freqs.items():
            freq_cnts[freq] += 1

        # 统计结果
        s = 0
        ans = 0
        for freq in range(len(freq_cnts) - 1, -1, -1):
            cnt = freq_cnts[freq]
            if cnt == 0:
                continue
            for _ in range(cnt):
                s += freq
                ans += 1
                if s >= n // 2:
                    return ans
        return -1
Share