首页 > 代码库 > 出现次数超过一半的数字

出现次数超过一半的数字

【问题】

题目:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。

【分析】

解法1:

先排序,排序后数组中间的那个元素就是要找的那个数字。时间复杂度O(n*logn)。

解法2:

既要缩小总的时间复杂度,那么可以用查找时间复杂度为O(1)的hash表,即以空间换时间。哈希表的键值(Key)为数组中的数字,值(Value)为该数字对应的次数。然后直接遍历整个hash表,找出每一个数字在对应的位置处出现的次数,输出那个出现次数超过一半的数字即可。

解法3:

咱们根据数组的特性考虑到:

  • 数组中有个数字出现的次数超过了数组长度的一半。换句话说,有个数字出现的次数比其他所有数字出现次数的和还要多。
  • 因此我们可以考虑在遍历数组的时候保存两个值:一个是数组中的一个数字,一个是次数,当我们遍历到下一个数字的时候:
    • 如果下一个数字和我们之前保存的数字相同,则次数加1;
    • 如果下一个数字和我们之前保存的数字不同,则次数减1;当次数减到0,我们需要保存下一个数字,并把次数重新设为1。

【代码】

#include <stdio.h>
#include <stdlib.h>

int FindNumber1(int *a, int len)//解法3
{
	int i;
	int candidate = a[0];
	int nTime = 1;
	for (i = 0; i < len; i++) {
		if (candidate == a[i])
			nTime++;
		else
			nTime--;
		if (nTime == 0) {
			candidate = a[i];
			nTime = 1;
		}
	}
	return candidate;
}

void q_sort(int *a, int start, int end)
{
	int tmp = a[start];
	int i = start, j = end;
	if (start + 1 > end)
		return;
	while (i < j) {
		while (i < j && a[j] > tmp)
			j--;
		if (i < j)
			a[i++] = a[j];
		while (i < j && a[i] < tmp)
			i++;
		if (i < j)
			a[j--] = a[i];
	}
	a[i] = tmp;
	q_sort(a, start, i - 1);
	q_sort(a, i + 1, end);
}

int FindNumber2(int *a, int len)//解法1
{
	q_sort(a, 0, len-1);
	return a[(len / 2)];
}


int main(void)
{
	int a[] = {0, 1, 1, 2, 1, 2, 2, 2, 2};
	int len = sizeof(a) / sizeof(int);
	int res;
	res = FindNumber1(a, len);
	printf("%d\n", res);
	res = FindNumber2(a, len);
	printf("%d\n", res);
	return 0;
}


出现次数超过一半的数字