题目(二叉搜索树的第 K 大节点)

题目：给定一棵二叉搜索树，请找出其中的第 K 大的节点。

算法思路

说到二叉搜索树，然后要求第 k 大的节点，即涉及到顺序问题，那么立即联想到二叉搜索树的中序遍历就是递增序列。因此只要对二叉搜索树进行中序遍历，记录中序序列中的第 K 个节点即可。算法可以有递归版和非递归版

算法实现

递归版

非递归版

复杂度

时间和空间复杂度均为 O(n)。

参考

[1] <<剑指offer2>>

题目一(数字在排序数组中出现的次数)

统计一个数字在排序数组中出现的次数。(默认递增)

算法思路

由于数组是递增有序的，那么数字如果重复一定都在一块，那么只需查找这个数字在数组中第一次出现的位置和最后一次出现的位置。接下来只要查找位置到，然后算出两位置间的距离即得所求。

那么对于有序数组要查找位置，什么方法最快呢？毫无疑问是二分查找，因为它可以在 O(logn) 时间内快速找到查找位置。

首先对于数字 k 第一次出现进行位置查找。如果中间的数大于 k，那么该位置在数组的前半段；如果中间的数小于 k，那么该位置在数组的后半段；如果中间的数等于 k，那么如果中间的数恰好是数组的起始位置，或者中间的数的前一个数字不是 k，也就是说，已经找到了目标位置，返回即可，否则该位置出现在数组的 前半段。

同理，对于数字 k 最后一次出现进行位置查找。如果中间的数大于 k，那么该位置在数组的前半段；如果中间的数小于 k，那么该位置在数组的后半段；如果中间的数等于 k，那么如果中间的数恰好是数组的末位位置，或者中间的数的下一个数字不是 k，也就是说，已经找到了目标位置，返回即可，否则该位置出现在数组 后半段。

注意：算法要鲁棒性好，要考虑功能测试、边界值测试和特殊输入测试。例如本题功能测试为数组中包含(不包含)要查找的数字，要查找的数字在数组中出现一次或多次；边界值测试如查找数组中的最大值和最小值，数组中只有一个数字；特殊值测试如输入数组为空。

算法实现

题目二(0-n-1 中缺失的数字)

一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0-n-1 之内。在范围 0-n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

算法思路

数组递增且查找元素，依然考虑二分查找思路。
首先，如果不存在缺失值，那么数组中的每个元素和它的下标是一一对应的。那么利用二分查找，如果中间元素的值和下标相等，那么下一轮只要查找右半边(前面元素均满足下标和元素值一一对应)；如果中间的元素值和下标不相等时，如果中间的位置在首位或者它的前一个元素和前一个元素的下标相等，那么中间的数字为所求；反之，它的前一个元素和前一个元素的下标不相等，那么下一轮只要查找左半边即可。

算法实现

题目三(数组中数组和下标相等的元素)

假设一个单调递增的数组中的每个元素都是整数并且是唯一的。请编写程序实现一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组{-3,-1,1,3,5} 中，数字 3 和它的下标相等。

算法思路

依然使用二分查找。
如果中间的元素刚好等于中间位置，那么立即返回所求；如果中间的元素小于中间位置，那么只需在右半段查找；否则在左半段查找即可。

算法实现

复杂度

题目一：由于算法都是通过二分查找两个位置，各自所需的时间复杂度均为 O(logn)，因而总的时间复杂度还是 O(logn)。空间复杂度为 O(1)。
题目二和三的时间复杂度均为 O(logn)，空间复杂度为 O(1)。

参考

[1] <<剑指offer2>>
[2] 牛客网

题目(两个链表的第一个公共结点)

输入两个链表，找出它们的第一个公共结点。

算法分析

两个链表的公共节点，即这个节点为两个链表的交汇点，而其两个链表的公共节点之后的所有节点均相同。那么这两个链表的拓扑形状看起来像一个 Y，那么现在问题就转成了如何找到这个交汇点。

算法思路一

可以利用两个栈分别存储两个链表的节点。然后，对这两个栈，两两出栈比较，并记录当前栈顶节点，比较直到顶底节点不同，停止算法。

算法思路二

对于两个不等长的链表，我们在长度较长的链表上让其工作指针先走两链表长度之差的步子，然后，两个链表的工作指针同时前进，直到遇到第一个公共节点即可。这个方法在前面的求链表是否有环的题目其实也有类似的应用。

算法实现一

算法实现二

复杂度

两个思路由于只对链表线性遍历，所以时间复杂度为O(m+n)。但思路一由于用到了两个栈，因而空间复杂度为O(n+m)，而后者为 O(1)，因此，算法思路二更优，但前者也是一个很好理解的思路。

参考

[1] <<剑指offer2>>
[2] 牛客网

题目(数组中的逆序对)

有一组数，对于其中任意两个数组，若前面一个大于后面一个数字，则这两个数字组成一个逆序对。请设计一个高效的算法，计算给定数组中的逆序对个数。
给定一个 int 数组 A 和它的大小 n，请返回A中的逆序对个数。保证 n 小于等于 5000。

算法思路

算法思想主要利用归并排序，唯一不同的主要在：当左边 i 位置所在的数大于右边 j 位置所在的数时，需要多算一步，即算出逆序对的个数，个数为 i 到 mid 之间的数字个数(i 为当前指向左部分的指针，j 为当前指向右部分的指针，mid 为两部分的中间位置)。

算法实现

复杂度

复杂度和归并排序相同。时间复杂度为 O(nlogn)，空间复杂度为 O(n)。

参考

[1] <<剑指offer2>>
[2] 牛客网

题目(第一次只出现一次的字符)

在字符串中找出第一个只出现一次的字符。如输入 “abaccdeff”，则输出 ‘b’。

题目一算法思路

利用 C++ 中自带的哈希表实现的数据结构 map 记录每个字符出现的次数，然后遍历此哈希表，得到第一个出现次数为 1 的字符即可。
另外，由于本题返回的类型是 char ，那么它有一个字节，8bit，即有256种可能，每个字母根据其 ASCII 码值作为数组的下标对应数组的一个数字，而数组中存储的是每个字符出现的次数。这样就创建了一个大小为256，简单且具有哈希特性的数组。

注：当所要哈希的字符有种数限制，如本题的256种，或者字母 a-z，则可以利用简单的数组来实现哈希特性。

题目二(字符流中第一次只出现一次的字符)

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 “go” 时，第一个只出现一次的字符是 “g”。当从该字符流中读出前六个字符 “google” 时，第一个只出现一次的字符是 “l”。
输出描述：如果当前字符流没有存在出现一次的字符，返回 # 字符。

题目二算法思路

本题，最简单的做法就是利用题目一的完整思路，但是需要不断更新字符串，做法较不友好，但是思想简单。
而本题的做法仍然利用大小为 256 的哈希数组来存储数据。但本题不再存储字符出现的次数，而是有设定的存储某些值。
首先未出现的字符都存入值 0，即数组中默认的初始值了；如果多次出现的字符统一存入负数，如-1；如果字符首次出现那么就存入其在字符串中的次序(从 1 开始计)。那么最后为了找出字符串中第一次只出现一次的字符，我们只需遍历哈希数组，找到哈希数组中值大于 0中最小的那个所对应的字符即可。

算法实现一

算法实现二

复杂度

题目一：算法仅遍历一次字符串，因此时间复杂度为 O(n)；定义了有限长度的容器，空间复杂度可算做 O(1)。
题目二：复杂度同上。

参考

[1] <<剑指offer2>>
[2] 牛客网