剑指offer第二十九题：数组中出现次数超过一半的数字
1 //============================================================================ 2 // Name : JZ-C-29.cpp 3 // Author : Laughing_Lz 4 // Version : 5 // Copyright : All Right Reserved 6 // Description : 数组中出现次数超过一半的数字 7 //============================================================================ 8 9 #include10 #include "Array.h" 11 #include 12 using namespace std; 13 14 bool g_bInputInvalid = false; 15 /** 16 *检查数组是否合法 17 */ 18 bool CheckInvalidArray(int* numbers, int length) { 19 g_bInputInvalid = false; 20 if (numbers == NULL && length <= 0) 21 g_bInputInvalid = true; 22 23 return g_bInputInvalid; 24 } 25 /** 26 * 检查数字出现次数是否大于数组长度一半 27 */ 28 bool CheckMoreThanHalf(int* numbers, int length, int number) { 29 int times = 0; 30 for (int i = 0; i < length; ++i) { 31 if (numbers[i] == number) 32 times++; 33 } 34 35 bool isMoreThanHalf = true; 36 if (times * 2 <= length) { 37 g_bInputInvalid = true; 38 isMoreThanHalf = false; 39 } 40 41 return isMoreThanHalf; 42 } 43 44 // ====================方法1:分治法，参考快速排序==================== 45 int MoreThanHalfNum_Solution1(int* numbers, int length) { 46 if (CheckInvalidArray(numbers, length)) { 47 return 0; 48 } 49 int middle = length >> 1; //右移1位 50 int start = 0; 51 int end = length - 1; 52 int index = Partition(numbers, length, start, end); 53 while (index != middle) { 54 if (index < middle) { 55 index = Partition(numbers, length, index + 1, end); 56 } else { 57 index = Partition(numbers, length, start, index - 1); 58 } 59 } 60 int result = numbers[middle]; 61 if (!CheckMoreThanHalf(numbers, length, result)) { 62 result = 0; 63 } 64 return result; 65 } 66 // ====================方法2:利用数字出现次数大于数组长度的一半==================== 67 int MoreThanHalfNum_Solution2(int* numbers, int length) { 68 if (CheckInvalidArray(numbers, length)) { 69 return 0; 70 } 71 int result = numbers[0]; 72 int times = 1; 73 for (int i = 1; i < length; i++) { 74 if (times == 0) { 75 result = numbers[i]; 76 times = 1; 77 } else if (result != numbers[i]) { 78 times--; 79 } else { 80 times++; 81 } 82 } 83 if (!CheckMoreThanHalf(numbers, length, result)) { 84 result = 0; 85 } 86 return result; 87 } 88 // ====================测试代码==================== 89 void Test(char* testName, int* numbers, int length, int expectedValue, 90 bool expectedFlag) { 91 if (testName != NULL) 92 printf("%s begins: \n", testName); 93 94 int* copy = new int[length]; 95 for (int i = 0; i < length; ++i) 96 copy[i] = numbers[i]; 97 98 printf("Test for solution1: "); 99 int result = MoreThanHalfNum_Solution1(numbers, length);100 if (result == expectedValue && g_bInputInvalid == expectedFlag)101 printf("Passed.\n");102 else103 printf("Failed.\n");104 105 printf("Test for solution2: ");106 result = MoreThanHalfNum_Solution2(copy, length);107 if (result == expectedValue && g_bInputInvalid == expectedFlag)108 printf("Passed.\n");109 else110 printf("Failed.\n");111 112 delete[] copy;113 }114 115 // 存在出现次数超过数组长度一半的数字116 void Test1() {117 int numbers[] = { 1, 2, 3, 2, 2, 2, 5, 4, 2 };118 Test("Test1", numbers, sizeof(numbers) / sizeof(int), 2, false);119 }120 121 // 不存在出现次数超过数组长度一半的数字122 void Test2() {123 int numbers[] = { 1, 2, 3, 2, 4, 2, 5, 2, 3 };124 Test("Test2", numbers, sizeof(numbers) / sizeof(int), 0, true);125 }126 127 // 出现次数超过数组长度一半的数字都出现在数组的前半部分128 void Test3() {129 int numbers[] = { 2, 2, 2, 2, 2, 1, 3, 4, 5 };130 Test("Test3", numbers, sizeof(numbers) / sizeof(int), 2, false);131 }132 133 // 出现次数超过数组长度一半的数字都出现在数组的后半部分134 void Test4() {135 int numbers[] = { 1, 3, 4, 5, 2, 2, 2, 2, 2 };136 Test("Test4", numbers, sizeof(numbers) / sizeof(int), 2, false);137 }138 139 // 输入空指针140 void Test5() {141 int numbers[] = { 1 };142 Test("Test5", numbers, 1, 1, false);143 }144 145 // 输入空指针146 void Test6() {147 Test("Test6", NULL, 0, 0, true);148 }149 150 int main(int argc, char** argv) {151 Test1();152 Test2();153 Test3();154 Test4();155 Test5();156 Test6();157 158 return 0;159 }
关于Partition方法：
1 // 《剑指Offer——名企面试官精讲典型编程题》代码 2 // 著作权所有者：何海涛 3 4 #include5 #include 6 #include "Array.h" 7 #include 8 9 // Random Partition10 int RandomInRange(int min, int max) {11 int random = rand() % (max - min + 1) + min;12 return random;13 }14 15 void Swap(int* num1, int* num2) {16 int temp = *num1;17 *num1 = *num2;18 *num2 = temp;19 }20 21 int Partition(int data[], int length, int start, int end) {22 if (data == NULL || length <= 0 || start < 0 || end >= length) {23 printf("Invalid Parameters");24 throw new std::exception();//这里括号里为什么不能加msg？？？！！！25 }26 int index = RandomInRange(start, end);27 Swap(&data[index], &data[end]);28 29 int small = start - 1;30 for (index = start; index < end; ++index) {31 if (data[index] < data[end]) {32 ++small;33 if (small != index)34 Swap(&data[index], &data[small]);35 }36 }37 38 ++small;39 Swap(&data[small], &data[end]);40 41 return small;42 }