首页 > 代码库 > 编程之美2.18 数组分割 原创解O(nlogn)的时间复杂度求解：
编程之美2.18 数组分割 原创解O(nlogn)的时间复杂度求解：
题目：有一个无序、元素个数为2n的正整数组，要求：如何能把这个数组分割为元素个数为n的两个数组，并使两个子数组的和最接近？
1 1 2 -> 1 1 vs 2
看题时，解法的时间复杂度一般都大于或等于O(n^2)。突然灵感一闪，发现一个新的解法，应该算是一个动态规划的过程吧，思路比较简单，请看代码。空间复杂度O(nlogn),时间复杂度O(n)。但是不能确定是否适用所有正整数组，如果有错，请给出你的测试用例，谢谢！
代码如下：
1 1 #include <iostream> 2 2 #include <vector> 3 3 using namespace std; 4 4 5 5 int compare(const void *in_iLeft, const void *in_iRight) { 6 6 int *a = (int*) in_iLeft; 7 7 int *b = (int*) in_iRight; 8 8 return *a - *b ; 9 9 10 10 }11 11 int main() {12 12 vector<int> t_Vec;13 13 int t_ivalue;14 14 int t_iLen = 0;15 15 cin >> t_ivalue;16 16 while(t_ivalue != 0) { //输入为0，则停止输入17 17 t_Vec.push_back(t_ivalue);18 18 t_iLen ++;19 19 cin >> t_ivalue;20 20 21 21 }22 22 int* t_pArr = new int[t_iLen];23 23 for(int i = 0; i < t_iLen; i++) {24 24 t_pArr[i] = t_Vec[i];25 25 } 26 26 qsort(t_pArr, t_iLen, sizeof(int), compare);27 27 int* t_pLeftArr = new int[t_iLen];28 28 int* t_pRightArr = new int[t_iLen];29 29 memset(t_pLeftArr, 0, t_iLen);30 30 memset(t_pRightArr, 0, t_iLen);31 31 int t_iSumLeft = t_pArr[t_iLen-1];32 32 int t_iSumRight = t_pArr[t_iLen-2];33 33 int t_iLeftIter = 1;34 34 int t_iRightIter = 1;35 35 t_pLeftArr[0] = t_pArr[t_iLen-1];36 36 t_pRightArr[0] = t_pArr[t_iLen-2];37 37 for(int i = t_iLen - 3; i >= 0 ; i --) {38 38 if(t_iSumLeft < t_iSumRight) {39 39 if(t_pArr[i] > 0) { 40 40 t_pLeftArr[t_iLeftIter ++] = t_pArr[i];41 41 t_iSumLeft += t_pArr[i];42 42 }else {43 43 t_pRightArr[t_iRightIter ++] = t_pArr[i];44 44 t_iSumRight += t_pArr[i];45 45 }46 46 }else {47 47 if(t_pArr[i] > 0) { 48 48 t_pRightArr[t_iRightIter ++] = t_pArr[i];49 49 t_iSumRight += t_pArr[i];50 50 }else {51 51 t_pLeftArr[t_iLeftIter ++] = t_pArr[i];52 52 t_iSumLeft += t_pArr[i];53 53 }54 54 }55 55 }56 56 cout << "打印原序列："<< endl;57 57 for(int i = 0; i < t_iLen; i ++) {58 58 if(t_pArr[i] != 0) {59 59 cout << t_pArr[i] << " ";60 60 }else {61 61 break;62 62 }63 63 }64 64 cout << endl;65 65 66 66 cout << "打印第一个序列：";67 67 for(int i = 0; i < t_iLeftIter; i ++) {68 68 if(t_pLeftArr[i] != 0) {69 69 cout << t_pLeftArr[i] << " ";70 70 }else {71 71 break;72 72 }73 73 }74 74 cout << endl;75 75 cout << "第一个序列合为:" << t_iSumLeft << endl;76 76 77 77 cout << "打印第二个序列：";78 78 for(int i = 0; i < t_iRightIter; i ++) {79 79 if(t_pRightArr[i] != 0) {80 80 cout << t_pRightArr[i] << " ";81 81 }else {82 82 break;83 83 }84 84 }85 85 cout << endl;86 86 cout << "第二个序列合为:" << t_iSumRight << endl; 87 87 t_Vec.clear();88 88 delete[] t_pArr;89 89 delete[] t_pLeftArr;90 90 delete[] t_pRightArr;91 91 system("pause"); 92 92 return 0;93 93 94 94 95 95 }
但是如果题目改成任意整数时你该怎么解答了呢？ ：）
编程之美2.18 数组分割 原创解O(nlogn)的时间复杂度求解：
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。