数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
#include<iostream>
#include<stdio.h>#include<stdlib.h>
using namespace std;
bool g_bInputInvalid = false;
bool CheckInvalidArray(int *num,int len)
{
g_bInputInvalid = false;
if(num == NULL && len <= 0)
g_bInputInvalid = true;
return g_bInputInvalid;
}
bool CheckMoreThanHalf(int *nums,int len,int num)
{
int times = 0;
for(int i = 0;i<len;++i)
{
if(nums[i] == num)
times++;
}
bool isMoreThanHalf = true;
if(times * 2 <= len)
{
isMoreThanHalf =false;
g_bInputInvalid = true;
}
return isMoreThanHalf;
}
int RandomInRange(int min,int max)
{
int random = rand() % (max - min + 1) + min;
return random;
}
void Swap(int *num1,int *num2)
{
int tmp = *num1;
*num1 = *num2;
*num2 = tmp;
}
int Partition(int data[],int len,int start,int end)
{
if(data == NULL || len <= 0 || start < 0 || end >= len)
printf("error\n");
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_1(int *nums,int len)
{
if(CheckInvalidArray(nums,len))
return 0;
int mid = len >> 1;
int start = 0;
int end = len -1;
int index = Partition(nums,len,start,end);
while(index != mid)
{
if(index > mid)
{
end = index -1 ;
index = Partition(nums,len,start,end);
}
else
{
start = index +1;
index = Partition(nums,len,start,end);
}
}
int ret = nums[mid];
if(!CheckMoreThanHalf(nums, len, ret))
ret = 0;
return ret;
}
int MoreThanHalfNum_2(int *nums,int len)
{
if(CheckInvalidArray(nums, len))
return 0;
int ret = nums[0];
int times = 1;
for(int i=1;i<len;++i)
{
if(times == 0)
{
ret = nums[i];
times = 1;
}
else if(nums[i] == ret)
times++;
else
times--;
}
if(!CheckMoreThanHalf(nums, len, ret))
ret = 0;
return ret;
}
void Test(char* testName, int* numbers, int length, int expectedValue, bool expectedFlag)
{
if(testName != NULL)
printf("%s begins: \n", testName);
int* copy = new int[length];
for(int i = 0; i < length; ++i)
copy[i] = numbers[i];
printf("Test for solution1: ");
int result = MoreThanHalfNum_1(numbers, length);
if(result == expectedValue && g_bInputInvalid == expectedFlag)
printf("Passed.\n");
else
printf("Failed.\n");
printf("Test for solution2: ");
result = MoreThanHalfNum_2(copy, length);
if(result == expectedValue && g_bInputInvalid == expectedFlag)
printf("Passed.\n");
else
printf("Failed.\n");
delete[] copy;
}
void Test1()
{
int numbers[] = {1, 2, 3, 2, 2, 2, 5, 4, 2};
Test("Test1", numbers, sizeof(numbers) / sizeof(int), 2, false);
}
void Test2()
{
//int numbers[] = {1, 2, 3, 2, 4, 2, 5, 2, 3};
int numbers[] = {1, 2, 3, 4, 8, 2, 5, 2, 3};
Test("Test2", numbers, sizeof(numbers) / sizeof(int), 0, true);
}
void Test3()
{
int numbers[] = {2, 2, 2, 2, 2, 1, 3, 4, 5};
Test("Test3", numbers, sizeof(numbers) / sizeof(int), 2, false);
}
void Test4()
{
int numbers[] = {1, 3, 4, 5, 2, 2, 2, 2, 2};
Test("Test4", numbers, sizeof(numbers) / sizeof(int), 2, false);
}
void Test5()
{
int numbers[] = {1};
Test("Test5", numbers, 1, 1, false);
}
void Test6()
{
Test("Test6", NULL, 0, 0, true);
}
int main()
{
// Test1();
Test2();
/* Test3();
Test4();
Test5();
Test6();
*/
return 0;
}