前言

编写算法，不仅需要正确实现，还需要考虑到时间效率的问题。比如采用更好的解法，养成更好的编程习惯。说到编程习惯，其实如果采用 C/C++ 编程时，在进行传递复杂类型参数的时，需要采用引用(或指针)，而要避免使用值传递，因为从形参到实参会产生一次多余的复制操作。用 Java、C# 等做多次字符串的拼接操作时，也不要多次使用 String 的 + 运算符来拼接字符串，因为这样会产生很多 String 临时实例，造成时间和空间的浪费。更好的办法是用 StringBuild 的 Append 方法来完成字符串的拼接。

题目(数组中出现次数超过一半的数字—牛客网)

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组{1,2,3,2,2,2,5,4,2}。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在则输出 0。

算法思路一

本题最简单的做法是先排序再求解，但是时间效率最低需要 O(nlogn)，以下思路时间效率都只需要 O(n)。

根据数组的特点：数组中有一个数字出现的次数超过数组长度的一半，也就是它出现的次数比其他所有数字出现的次数之和还要多。那么我们采用采用阵地攻守的思想：第一个数字作为第一个士兵，守阵地，计数为 1。如果遇到相同的数字，计数加 1，如果遇到不相同元素，即为敌人，同归于尽,计数减 1；当计数值为 0 时，表示没有士兵了，又以新的 i 值作为守阵地的士兵。最后一个留在阵地的士兵有可能就是主元素，即所求，所以只需验证即可，可再加一次循环，记录这个士兵的个数看是否大于数组一半即可。

算法思路二

根据数组的特点：数组中有一个数字出现的次数超过数组长度的一半，那么当数字有序的时候，所求的数字一定在有序数组的中位数上。假设中位数的索引为 k，那么现在问题就转为为求数组中第 k 大的数字了，而这个转换问题可利用快速排序的思想，在线性时间内得到解决。

算法实现一

算法实现二

参考

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