数组中出现次数超过一半的数字 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

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

1. 使用快速排序(QuickSort)的方法, 把中值(middle)和索引(index)匹配, 输出中值, 并检测是否符合要求.

2. 使用计数方法依次比较.

代码: 

方法1:

/*
 * main.cpp
 *
 *  Created on: 2014.6.12
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

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

int RandomInRange(int min, int max)
{
    int random = rand() % (max - min + 1) + min;
    return random;
}

void Swap(int* num1, int* num2)
{
    int temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

int Partition(int data[], int length, int start, int end)
{
    if(data =http://www.mamicode.com/= NULL || length <= 0 || start < 0 || end >= length) {>

方法2:
/*
 * main.cpp
 *
 *  Created on: 2014.6.12
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

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

bool CheckMoreThanHalf (int* numbers, int length, int number) {
	int times = 0;
	for (int i=0; i<length; ++i) {
		if (numbers[i] == number)
			times++;
	}
	if (times*2 < length)
		return false;
	return true;
}

int MoreThanHalfNum (int* numbers, int length) {
	if (numbers == NULL || length <= 0)
		return 0;
	int result = numbers[0];
	int times = 1;
	for (int i=0; i<length; ++i) {
		if (times == 0) {
			result = numbers[i];
			times = 1;
		}
		if (numbers[i] == result) times++;
		else times--;
	}
	if (!CheckMoreThanHalf(numbers, length, result))
		return 0;
	return result;
}

int main(void)
{
    int str[] =  {1, 2, 3, 2, 2, 2, 5, 2, 4};
    int result = MoreThanHalfNum(str, 9);
    printf("reuslt = %d\n", result);

    return 0;
}



输出:
reuslt = 4