本文共 5667 字，大约阅读时间需要 18 分钟。
剑指offer第三十题：最小的k个数
1 //============================================================================ 2 // Name : JZ-C-30.cpp 3 // Author : Laughing_Lz 4 // Version : 5 // Copyright : All Right Reserved 6 // Description : 最小的k个数 7 //============================================================================ 8 9 #include 10 #include 11 #include 12 #include 13 #include "Array.h" 14 using namespace std; 15 16 using namespace std; 17 18 // ====================方法1:同样可利用分治法==================== 19 void GetLeastNumbers_Solution1(int* input, int n, int* output, int k) 20 { 21 if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0) 22 return; 23 24 int start = 0; 25 int end = n - 1; 26 int index = Partition(input, n, start, end); 27 while(index != k - 1) 28 { 29 if(index > k - 1) 30 { 31 end = index - 1; 32 index = Partition(input, n, start, end); 33 } 34 else 35 { 36 start = index + 1; 37 index = Partition(input, n, start, end); 38 } 39 } 40 41 for(int i = 0; i < k; ++i) 42 output[i] = input[i];//查找后，放入output数组 43 } 44 45 // ====================方法2:堆、红黑树：set、multiset都是基于红黑树实现的==================== 46 typedef multiset
> intSet; 47 typedef multiset
>::iterator setIterator; 48 49 void GetLeastNumbers_Solution2(const vector
& data, intSet& leastNumbers, int k) 50 { 51 leastNumbers.clear(); 52 53 if(k < 1 || data.size() < k) 54 return; 55 56 vector
::const_iterator iter = data.begin(); 57 for(; iter != data.end(); ++ iter) 58 { 59 if((leastNumbers.size()) < k) 60 leastNumbers.insert(*iter); 61 62 else 63 { 64 setIterator iterGreatest = leastNumbers.begin(); 65 66 if(*iter < *(leastNumbers.begin())) 67 { 68 leastNumbers.erase(iterGreatest); 69 leastNumbers.insert(*iter); 70 } 71 } 72 } 73 } 74 75 // ====================测试代码==================== 76 void Test(char* testName, int* data, int n, int* expectedResult, int k) 77 { 78 if(testName != NULL) 79 printf("%s begins: \n", testName); 80 81 vector
vectorData; 82 for(int i = 0; i < n; ++ i) 83 vectorData.push_back(data[i]); 84 85 if(expectedResult == NULL) 86 printf("The input is invalid, we don't expect any result.\n"); 87 else 88 { 89 printf("Expected result: \n"); 90 for(int i = 0; i < k; ++ i) 91 printf("%d\t", expectedResult[i]); 92 printf("\n"); 93 } 94 95 printf("Result for solution1:\n"); 96 int* output = new int[k]; 97 GetLeastNumbers_Solution1(data, n, output, k); 98 if(expectedResult != NULL) 99 {100 for(int i = 0; i < k; ++ i)101 printf("%d\t", output[i]);102 printf("\n");103 }104 105 delete[] output;106 107 printf("Result for solution2:\n");108 intSet leastNumbers;109 GetLeastNumbers_Solution2(vectorData, leastNumbers, k);110 printf("The actual output numbers are:\n");111 for(setIterator iter = leastNumbers.begin(); iter != leastNumbers.end(); ++iter)112 printf("%d\t", *iter);113 printf("\n\n");114 }115 116 // k小于数组的长度117 void Test1()118 {119 int data[] = { 4, 5, 1, 6, 2, 7, 3, 8};120 int expected[] = { 1, 2, 3, 4};121 Test("Test1", data, sizeof(data) / sizeof(int), expected, sizeof(expected) / sizeof(int));122 }123 124 // k等于数组的长度125 void Test2()126 {127 int data[] = { 4, 5, 1, 6, 2, 7, 3, 8};128 int expected[] = { 1, 2, 3, 4, 5, 6, 7, 8};129 Test("Test2", data, sizeof(data) / sizeof(int), expected, sizeof(expected) / sizeof(int));130 }131 132 // k大于数组的长度133 void Test3()134 {135 int data[] = { 4, 5, 1, 6, 2, 7, 3, 8};136 int* expected = NULL;137 Test("Test3", data, sizeof(data) / sizeof(int), expected, 10);138 }139 140 // k等于1141 void Test4()142 {143 int data[] = { 4, 5, 1, 6, 2, 7, 3, 8};144 int expected[] = { 1};145 Test("Test4", data, sizeof(data) / sizeof(int), expected, sizeof(expected) / sizeof(int));146 }147 148 // k等于0149 void Test5()150 {151 int data[] = { 4, 5, 1, 6, 2, 7, 3, 8};152 int* expected = NULL;153 Test("Test5", data, sizeof(data) / sizeof(int), expected, 0);154 }155 156 // 数组中有相同的数字157 void Test6()158 {159 int data[] = { 4, 5, 1, 6, 2, 7, 2, 8};160 int expected[] = { 1, 2};161 Test("Test6", data, sizeof(data) / sizeof(int), expected, sizeof(expected) / sizeof(int));162 }163 164 // 输入空指针165 void Test7()166 {167 int* expected = NULL;168 Test("Test7", NULL, NULL, expected, 0);169 }170 171 int main(int argc, char** argv)172 {173 Test1();174 Test2();175 Test3();176 Test4();177 Test5();178 Test6();179 Test7();180 181 return 0;182 }
1 // 《剑指Offer——名企面试官精讲典型编程题》代码 2 // 著作权所有者：何海涛 3 4 #include 5 #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 }