算法与数据结构练习题，c++如何找出数组中出现次数超过一半的数字。
算法题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入数组{ 1, 2, 3, 2, 2, 2, 5, 4, 2 }，则输出数字2。
解法1：基于快排思想的O(n)算法
数组里面有一个数字x出现的次数超过了数组长度的一半，那么排序之后位于数组中间的数字一定就是x。受快排算法的启发，先在数组中随机选择一个数字，然后调整数组中数字的排序，使得比选中数字小的都排在它左边，比选中数字大的都排在它的右边。如果这个选中的数字刚好是数组的中位数（即长度为n的数组中第n/2大的数字），则问题得解。不然，排序后它的下标大于n/2，则中位数位于它的左边，继续在它的左边找。如果下标小于n/2，那么中位数位于它的右边，继续在它的右边找。
参考代码实例：
// 返回调整后基准数的位置
int Partition(int data[], int length, int start, int end)
{
if(data == NULL || length <= 0 || start < 0 || end >= length)
throw new std::exception(“Invalid Parameters”);
int index = RandomInRange(start, end);
Swap(&data[index], &data[end]);
int small = start – 1;
for(index = start; index < end; ++ index)
{
if(data[index] < data[end])
{
++ small;
if(small != index)
Swap(&data[index], &data[small]);
}
}
++ small;
Swap(&data[small], &data[end]);
return small;
}
int MoreThanHalfNum_Solution1(int* numbers, int length)
{
if(CheckInvalidArray(numbers, length))
return 0;
int middle = length >> 1;
int start = 0;
int end = length – 1;
int index = Partition(numbers, length, start, end);
while(index != middle)
{
if(index > middle)
{
end = index – 1;
index = Partition(numbers, length, start, end);
}
else
{
start = index + 1;
index = Partition(numbers, length, start, end);
}
}
int result = numbers[middle];
if(!CheckMoreThanHalf(numbers, length, result))
result = 0;
return result;
}
只贴出了比较关键的MoreThanHalfNum_Solution1()和Partition()函数。学习过快排算法的同学应该可以够理解Partition()函数。在Partition()函数中，首先选取了一个随机数(称为r)，然后把r交换到了数组尾部。接着的for循环将大于r的数字向后移，小于r的数字向前移。变量small是用来记录当前一共扫到了多少个比r小的数字。这样for循环中的Swap(…)就是将左起第一个比r大的数字(data[small])和它后面第一个比r小的数字进行交换。这样for循环结束之后，所有比r大的数字全部移动到了数组尾部，r之前。然后Partition()函数中的最后一个Swap用来将r与左起第一个比r大的数字(data[small])进行交换，比如是：1、2、2、3、5、6、6、7、4，就是将5与4交换。这样最终随机数r左边的数字都比它小，右边的数字都比它大，最后返回r的位置。
注意：快排算法的平均时间复杂度是O(nlogn)，而上面的代码只是寻找中位数，并不是给数组完全排序，它的时间复杂度是O(n)。
解法二：根据数组特点找出O(n)的算法
是更好的解法，也更简单。遍历数组，并且保存两个值：一个是数组中的一个数字，一个是次数。当遍历下一个数字时，如果下一个数字和当前保存的数字相同，则次数加1；如果不同则次数减1。如果次数为0，则需要保存下一个数字，并把次数设为1。由于要找的数字出现的次数比其他所有数字出现的次数之和还要多，所以要找的数字肯定是最后一次把次数设为1的那个数字。
参考代码：
int MoreThanHalfNum_Solution2(int* numbers, int length)
{
if(CheckInvalidArray(numbers, length))
return 0;
int result = numbers[0];
int times = 1;
for (int i = 1; i < length; ++i)
{
if (times == 0)
{
result = numbers[i];
times = 1;
}
else if (numbers[i] == result)
times++;
else
times–;
}
if (!CheckMoreThanHalf(numbers, length, result))
result = 0;
return result;
}
这种解法真的太奇妙了，既容易理解，实现代码又简洁。
《剑指Offer》读书笔记