总结两道面试题：
题目1：在n个数中寻找第k大的数
具体思路如下：
- 使用选择或冒泡法，排出前k个数，然后选择第k个数，时间复杂度为O(kn)
- 使用快速排序，将n个数排序，然后选择第k个数，时间复杂度为O(nlogn)
- 使用长度为k的数组存储前面k个数，然后排序，时间复杂度为O(klogk)；然后对后面n-k个元素进行插入操作，复杂度为(n-k)logk。总的时间复杂度为O(nlogk)。
- 使用节点数为k的小根堆（注意这里不是大根堆），堆排序时间复杂度为O(klogk)；然后对后面n-k个元素进行插入操作，复杂度为(n-k)logk。总的时间复杂度为O(nlogk)。
- 使用快排思路。选出一个数X，把数组分成比X小的左边和比X大的右边这两部分，按如下递归：
如果左边的个数小于k-1，则在右边寻找；
如果左边的个数大于k-1，则在左边寻找；
如果左边的个数等于k-1，则这个数即为第k大的数。
时间复杂度为O(n)。推导：
最差情况如下：假设快排每次都平均划分，但是都不在枢纽元素上找到第k大
第一趟快排没找到，时间复杂度为O(n)，第二趟也没找到，时间复杂度为O(n/2)，……，第k趟找到，时间复杂度为O(n/2^k)，所以总的时间复杂度为O(n(1+1/2+….+1/2^k))=O(2n)，即O(n)。
题目2：只遍历一次，在一个字符串中找到第一个只出现一次的字符，如输入abaccdeff，则输出b。其中，字符的个数为k个，字符串的长度为n，k<<n
具体思路如下：
- 如果不要求遍历次数。
可以从头开始取一个字符，将其与后面字符依次进行比较，如果有相同的字符说明它不是只出现一次的字符。当第一次出现遍历完且没有重复字符出现的情况时，表明这个字符就是第一个只出现一次的字符。时间复杂度为O(n^2)。
也可以做一个Hash表来记录这个字符串中每个字符出现的次数，遍历完第一次就可以得到字符次数。然后再遍历第二次，当Hash表中对应字符的值为1时，表明这个字符就是第一个只出现一次的字符。时间复杂度为O(2n)。 - 关键要解决的是字符次数信息和字符顺序信息。
方法1：Hash表+数组或链表
Hash表+数组：Hash表来记录字符出现的次数。在遍历字符串过程中，如果Hash表中存在对应字符，则删除数组中对应字符且Hash表中对应字符的值加1或者置于NULL，如果不存在则在Hash表中记录且插入到数组末尾。遍历完之后得到的数组第一个元素就是第一个只出现一次的字符。
由于数组查找方便，插入、删除元素不方便；而链表查找不方便，添加、删除元素方便，所以也可以使用链表来替换数组。
Hash表+链表：Hash表来记录字符在链表中的节点指针。在遍历字符串过程中，如果Hash表中存在对应字符，则删除链表中对应节点且Hash表中对应字符的值加1或者置于NULL，如果不存在则在Hash表中记录且插入到链表末尾。遍历完之后得到的数组第一个元素就是第一个只出现一次的字符。
方法2：两个数组
一个数组记录字符的次数信息，一个数组记录字符的顺序信息。
在遍历字符串过程中，如果记录字符顺序信息的数组中存在对应字符，则记录字符次数的数组对应位置上加1，否则，在记录字符顺序信息的数组末尾插入该字符且在记录字符次数的数组某位插入1。
遍历完之后，在记录字符次数的数组找到第一个1出现的位置，在记录字符顺序信息的数组中找到对应位置的元素即为第一个只出现一次的字符。
当然，“两个数组”的办法，可以把问题扩展为： 只遍历一次，在一个字符串中找到第一个只出现N次的字符。
