某花心男外面有了情妇，他的QQ上超过半数的聊天记录都是和那情妇对话，也就是说聊天记录中排除花心男自己讲的话之后，他情妇的聊天记录超过其他人的总和。很不巧，那个花心男的老婆通过特殊渠道取得了他老公的所有QQ聊天记录msgList（结构为LinkList，每个数组项包含属性qqNumber、content、time，约有几十万条数据），现在需要你编个程序把那个情妇的名字给找出来。
说白了，就是找出数组中出现次数超过半数的那个元素。这里假设msgList只包含情妇和其他人的记录（不包括花心男），因为直接删了花心男的数据也只需时间复杂度o(n)，不影响。
解法一：
这是最容易想到的一种方法，也就是遍历msgList，用一个countMap记录每个qqNumber出现的次数，然后遍历countMap的keySet，找出出现次数最多的那个qqNumber。
这种方法的时间复杂度为o(n)，空间复杂度为o(n)。
解法二：
虽然上面的算法时间复杂度已经是o(n)，但是很费空间，因为n不是个小数目。另一种方法是对msgList的qqNumber进行快速排序，由于情妇的qqNumber出现超过半数，则排序后数组的中数必定是情妇的qqNumber~~~问题解决~~~~
这种方法的时间复杂度为o(nlogn)，空间复杂度为o(1)。
解法三：
好吧，上面两种解法都很不错了，但还能有更好的吗？复杂度为o(n)，空间复杂度为o(1)的？
答案是，有的。
每次在msgList里面删除两个不同qqNumber，直到无法再删为止。由于情妇的聊天记录超过半数，所以最后生还的qqNumber肯定是她的。
这种方法的时间复杂度为o(n)，空间复杂度为o(1)。
