1， (Huffman) 给定字符串”ABACCADCACCDCDA”, 选择各个字符合适的二进制表示，使得： （1） 没有一个表示是另一个表示的前缀； （2） 原字符串的总二进制表示最短。 2， 给定一个数组，找到其中第k小的元素。

1. 首先统计字符串中每个字符出现的次数，得到如下表格：

| 字符 | A | B | C | D |
|------|---|---|---|---|
| 频数 | 3 | 2 | 5 | 4 |

2. 将每个字符作为一个叶子节点，构建哈夫曼树，得到如下图所示的二叉树：

         +
        / \
       /   \
      +     D
     / \
    /   \
   A     +
        / \
       /   \
      C     B

3. 从根节点出发，向左子树走记为0，向右子树走记为1，得到每个字符的二进制表示：

| 字符 | A | B | C | D |
|------|---|---|---|---|
| 编码 | 00 | 10 | 11 | 01 |

4. 将原字符串中的每个字符按照上表中的编码进行替换，得到最终的压缩字符串为：

0001101101111111000100011101101110111010

5. 验证无前缀性：从根节点开始，依次走过压缩字符串中的每个字符，如果走到的节点是叶子节点，就输出对应的字符，重复此过程直到压缩字符串结束。根据上表可知，任何一个字符的编码都不是另一个字符编码的前缀，因此可以正确解压缩。

6. 验证最短性：假设使用ASCII码对每个字符进行编码，则原字符串的总长度为16个字符 * 8个比特位/字符 = 128个比特位。而使用哈夫曼编码进行压缩后，总长度为

3 * 2 + 2 * 2 + 5 * 2 + 4 * 2 = 28

个比特位，远小于原字符串的长度，说明使用哈夫曼编码可以得到更短的压缩字符串。

2. 给定一个数组，找到其中第k小的元素可以使用快速选择算法，其基本思想是通过类似快速排序的分治思想，每次选取一个元素作为“枢纽”，将数组划分为比它小的一部分和比它大的一部分，如果枢纽的位置正好是第k小的元素，则直接返回，否则根据枢纽的位置，递归地在左边或右边的部分中继续查找第k小的元素。快速选择算法的时间复杂度为O(n)，最坏情况下为O(n^2)，但可以通过随机选择枢纽的方式避免最坏情况的出现。