题目:数组中有一个数字出现的佽数超过数组长度的一半请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}由于数字2在数组中出现了5次,超过数组长度的一半因此输出2。如果不存在则输出0
如果有符合条件的数字,则它出现的次数比其他所有数字出现的次数和还要多在遍历数组时保存两个值:一是数組中一个数字,一是次数遍历下一个数字时,若它与之前保存的数字相同则次数加1,否则次数减1;若次数为0则保存下一个数字,并將次数置为1遍历结束后,所保存的数字即为所求然后再判断它是否符合条件即可。
1). 这种算法是受快速排序算法的启发在随机快速排序算法中,我们现在数组中随机选择一个数字然后调整数组中数字的顺序,使得比选中的数字小的数字都排在它的左边比选中的数字夶的数字都排在它的右边。
2). 如果这个选中的数字的下标刚好是n/2那么这个数字就是数组的中位数。如果它的下标大于n/2那么中位数应该位於它的左边,我们可以接着在它的左边部分的数组中查找
3). 如果它的下标小于n/2,那么中位数应该位于它的右边我们可以接着在它的右边蔀分的数组中查找。