题目:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。
思路:一个数字在数组中出现次数超过了一半,则排序后,位于数组中间的数字一定就是该出现次数超过了长度一半的数字(,也即是说,这个数字就是统计学上的中位数。事实上可以不用对数组进行排序,或者说仅部分排序,受快速排序的partition函数的启发,我们可以利用反复调用partition函数来求的该数字。我们现在数组中随机选取一个数字,而后通过Partition函数返回该数字在数组中的索引index,如果index刚好等于n/2,则这个数字便是数组的中位数,也即是要求的数,如果index大于n/2,则中位数肯定在index的左边,在左边继续寻找即可,反之在右边寻找。这样可以只在index的一边寻找,而不用两边都排序,减少了一半排序时间。
1 #include<stdio.h> 2 #include<iostream> 3 #include<stdlib.h> 4 5 //生成一个在start和end之间的随机数 6 int RandomInRange(int min, int max) 7 { 8 int random = rand() % (max - min + 1) + min; 9 return random; 10 } 11 12 //交换两个数 13 void Swap(int* num1, int* num2) 14 { 15 int temp = *num1; 16 *num1 = *num2; 17 *num2 = temp; 18 } 19 20 //选择一个数字,把数组分成两部分 21 int Partition(int data[], int length, int start, int end) 22 { 23 if(data == NULL || length <= 0 || start < 0 || end >= length) 24 // throw new std::exception("Invalid Parameters"); 25 exit(1); 26 27 int index = RandomInRange(start, end); 28 Swap(&data[index], &data[end]); 29 30 int small = start - 1; 31 for(index = start; index < end; ++ index) 32 { 33 if(data[index] < data[end]) 34 { 35 ++ small; 36 if(small != index) 37 Swap(&data[index], &data[small]); 38 } 39 } 40 41 ++ small; 42 Swap(&data[small], &data[end]); 43 44 return small; 45 } 46 47 bool g_bInputInvalid = false; 48 49 //检查输入数组的有效性 50 bool CheckInvalidArray(int* numbers, int length) 51 { 52 g_bInputInvalid = false; 53 if(numbers == NULL && length <= 0) 54 g_bInputInvalid = true; 55 56 return g_bInputInvalid; 57 } 58 59 //检查输入数组中出现最高的数字次数是否超过数组长度的一半 60 bool CheckMoreThanHalf(int* numbers, int length, int number) 61 { 62 int times = 0; 63 for(int i = 0; i < length; ++i) 64 { 65 if(numbers[i] == number) 66 times++; 67 } 68 69 bool isMoreThanHalf = true; 70 if(times * 2 <= length) 71 { 72 g_bInputInvalid = true; 73 isMoreThanHalf = false; 74 } 75 76 return isMoreThanHalf; 77 } 78 79 80 int MoreThanHalfNum(int* numbers, int length) 81 { 82 if(CheckInvalidArray(numbers, length)) 83 return 0; 84 85 int middle = length >> 1; 86 int start = 0; 87 int end = length - 1; 88 int index = Partition(numbers, length, start, end); 89 while(index != middle) 90 { 91 if(index > middle) 92 { 93 end = index - 1; 94 index = Partition(numbers, length, start, end); 95 } 96 else 97 { 98 start = index + 1; 99 index = Partition(numbers, length, start, end); 100 } 101 } 102 103 int result = numbers[middle]; 104 if(!CheckMoreThanHalf(numbers, length, result)) 105 result = 0; 106 107 return result; 108 } 109 110 int main() 111 { 112 int numbers[] = {1,2,3,2,2,2,5,4,2}; 113 int length = sizeof(numbers) / sizeof(int); 114 printf("Test for solution: "); 115 int result = MoreThanHalfNum(numbers, length); 116 if(g_bInputInvalid == false) 117 printf("%d \n", result); 118 else 119 printf("Failed.\n"); 120 }