C語言實(shí)現(xiàn)在數(shù)組A上有序合并數(shù)組B的方法
本文實(shí)例講述了C語言實(shí)現(xiàn)在數(shù)組A上有序合并數(shù)組B的方法,分享給大家供大家參考。具體分析如下:
題目:數(shù)組A和數(shù)組B均有序,數(shù)組A有足夠大內(nèi)存來容納數(shù)組B,將數(shù)組B有序合并到數(shù)組A中
分析:如果由前至后合并,復(fù)雜度將會(huì)是O(N2),這樣的復(fù)雜度顯然不是最優(yōu)解,利用兩個(gè)指針指向兩個(gè)數(shù)組的尾部,從后往前遍歷,這樣的復(fù)雜度為O(n2)
由此可以寫出下面的代碼:
#include <iostream> #include <algorithm> #include <iterator> using namespace std; int arrayA[10] = {1, 3, 5, 7, 9}; int arrayB[] = {2, 4, 6, 8, 10}; const int sizeB = sizeof arrayB / sizeof *arrayB; const int sizeA = sizeof arrayA / sizeof *arrayA - sizeB; int* mergeArray(int *arrayA, int sizeA, int *arrayB, int sizeB) { if (arrayA == NULL || arrayB == NULL || sizeA < 0 || sizeB < 0) return NULL; int posA = sizeA - 1; int posB = sizeB - 1; while (posA >= 0 && posB >= 0) { if (arrayA[posA] < arrayB[posB]) { arrayA[posA + posB + 1] = arrayB[posB]; posB--; } else { arrayA[posA + posB + 1] = arrayA[posA]; posA--; } copy(arrayA, arrayA + 10, ostream_iterator<int>(cout, " ")); system("pause"); } return arrayA; } void main() { int *result = mergeArray(arrayA, sizeA, arrayB, sizeB); copy(result, result + 10, ostream_iterator<int>(cout, " ")); cout << endl; }
代碼寫完后似乎完成了所需功能,但還不止于此,必須對(duì)上述代碼做UT
1. 健壯性
arrayA或arrayB為空,長(zhǎng)度小于0
2. 邊界用例
arrayA為空,長(zhǎng)度為1;arrayB不為空,長(zhǎng)度大于1
首元素用例
const int size = 6;
int arrayA[size] = {2};
int arrayB[] = {0, 1, 1, 1, 1};
反之
const int size = 6;
int arrayA[size] = {0, 1, 1, 1, 1};
int arrayB[] = {2};
3. 正常用例:
const int size = 10;
int arrayA[size] = {1, 3, 5, 7, 9};
int arrayB[] = {2, 4, 6, 8, 10};
const int size = 10;
int arrayA[size] = {2, 4, 6, 8, 10};
int arrayB[] = {1, 3, 5, 7, 9};
const int size = 10;
int arrayA[size] = {1, 2, 3, 4, 5};
int arrayB[] = {6, 7, 8, 9, 10};
const int size = 10;
int arrayA[size] = {6, 7, 8, 9, 10};
int arrayB[] = {1, 2, 3, 4, 5};
經(jīng)過上面的測(cè)試,不難發(fā)現(xiàn)在邊界條件用例中,代碼已經(jīng)不能正確運(yùn)行出結(jié)果,在測(cè)試用例的驅(qū)動(dòng)下,不難寫出正確代碼如下:
int* mergeArray(int *arrayA, int sizeA, int *arrayB, int sizeB) { if (arrayA == NULL || arrayB == NULL || sizeA < 0 || sizeB < 0) return NULL; int posA = sizeA - 1; int posB = sizeB - 1; while (posA >= 0 && posB >= 0) { if (arrayA[posA] < arrayB[posB]) { arrayA[posA + posB + 1] = arrayB[posB]; posB--; } else { arrayA[posA + posB + 1] = arrayA[posA]; posA--; } copy(arrayA, arrayA + size, ostream_iterator<int>(cout, " ")); system("pause"); } //出現(xiàn)兩種情形: //1. posA < 0 && posB >= 0 //2. posA >= 0 && posB < 0 //只有第1種情形需要進(jìn)行處理 if (posA < 0 && posB >= 0) { while (posB >= 0) { arrayA[posA + posB + 1] = arrayB[posB]; posB--; } } return arrayA; }
相信本文所述對(duì)大家C程序算法設(shè)計(jì)的學(xué)習(xí)有一定的借鑒價(jià)值。
相關(guān)文章
C語言實(shí)現(xiàn)簡(jiǎn)單的掃雷游戲操作
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡(jiǎn)單的掃雷游戲操作,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-03-03c++?qt自定義搜索編輯框的實(shí)現(xiàn)方法
這篇文章主要介紹了c++?qt自定義搜索編輯框,通過自定義QLineEdit,在編輯框里添加布局,將按鈕設(shè)置在右邊,當(dāng)點(diǎn)擊按鈕搜索按鈕時(shí)發(fā)送信號(hào)到主界面做相應(yīng)的操作,需要的朋友可以參考下2022-03-03C++ string和wstring相互轉(zhuǎn)換方式
這篇文章主要介紹了C++ string和wstring相互轉(zhuǎn)換方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-02-02C++實(shí)現(xiàn)三子棋游戲詳細(xì)介紹(附代碼)
大家好,本篇文章主要講的是C++實(shí)現(xiàn)三子棋游戲詳細(xì)介紹,感興趣的同學(xué)趕快來看一看吧,對(duì)你有幫助的話記得收藏一下2022-01-01C++版本基于ros將文件夾中的圖像轉(zhuǎn)換為bag包
這篇文章主要介紹了C++版本基于ros將文件夾中的圖像轉(zhuǎn)換為bag包,本文通過圖文并茂的形式給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-01-01