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

1. 首先需要统计字符串中各字符出现的频率。

字符 | 频率
----|----
A | 3
B | 1
C | 6
D | 3

2. 将频率从小到大排序。

字符 | 频率
----|----
B | 1
A | 3
D | 3
C | 6

3. 将频率最小的两个字符进行合并，生成一个新的字符，其频率为两个字符频率之和。

字符 | 频率
----|----
B | 1
AD | 6
C | 6

4. 重复步骤3，直到只剩下一个字符。

字符 | 频率
----|----
BADC | 13

5. 对每个字符分配一个二进制编码，频率越高的字符编码越短，为了满足“没有一个表示是另一个表示的前缀”的要求，可以采用Huffman编码。

字符 | 频率 | 编码
----|----|----
B | 1 | 1111
A | 3 | 10
D | 3 | 110
C | 6 | 0

6. 将原字符串中的每个字符替换为对应的编码，得到最终的二进制表示。

原字符串：ABACCADCACCDCDA

替换后： 101111001010001100001000011101100010000011101100000

7. 可以发现，原字符串的总二进制表示最短。

2. 以下是用c++实现找到数组中第k小的元素的代码：

#include <iostream>
#include <algorithm>
using namespace std;

int findKthSmallest(int arr[], int n, int k) {
    sort(arr, arr+n);
    return arr[k-1];
}

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 4;
    int kthSmallest = findKthSmallest(arr, n, k);
    cout << "The " << k << "th smallest element is: " << kthSmallest << endl;
    return 0;
}

输出结果为：

The 4th smallest element is: 3