Dãy sắp xếp tạo ra từ hai dãy sắp xếp (Microsoft)

[chiquang1498]

Cho hai dãy số đã được sắp xếp A[], B[]. Hãy in ra rất cả các dãy số đã được sắp xếp theo nguyên tắc: phần tử đầu tiên thuộc A[], phần tử tiếp theo thuộc B[]….
Ví dụ với dãy A[] = {10, 15, 25}, B[] = {1, 5, 20, 30 } ta sẽ có các dãy số được tạo ra theo nguyên tắc trên như sau:
10 20
10 20 25 30
10 30
15 20
15 20 25 30
15 30
25 30
p/s: Mọi người cho e ý tưởng với ạ. E cần ý tưởng nào đó tối ưu vì submit với thời gian O(n^2) sẽ không vượt qua được test!

[tungnt999]

Theo mình thì có thể làm như này:

Step 1: đưa data vào array trong đó mỗi phần tử chứa value và original array (A or B)
output: C = { (10, A), (15, A), (20, B), (25, A), (30, B) }

Step 2: Duyệt cái array này 1 phần tử A cho đến hết dãy, đủ cặp nào in ra cặp đó
output cho lần duyệt đầu tiên từ phần tử C[0]:
10 20
10 20 25 30

Step 3: Lặp lại Step 2 từ phần tử A tiếp theo, đến khi ko còn phần tử A nào nữa là xong

[tungnt999]

Đây là code mình viết bạn có thể tham khảo.

#include "stdafx.h" #include <deque>#include <iostream> using namespace std; typedef struct Elem {    Elem(int val, bool isA) : value(val), isArrayA(isA), isFirstB(true) {}    int value;    bool isArrayA;    bool isFirstB;} Element; class CCombination {public:    CCombination(unsigned int sizeA, int *a, unsigned int sizeB, int *b);    ~CCombination();     void Combine();    void PrintResult(); private:    int *arrA, *arrB;    unsigned int uiSizeA, uiSizeB;    deque <Element> orgQue;    deque <int> orgResQue;}; CCombination::CCombination(unsigned int sizeA, int *aA, unsigned int sizeB, int *aB)    : uiSizeA(sizeA), uiSizeB(sizeB){    arrA = new int[uiSizeA];    arrB = new int[uiSizeB];    memcpy((void*)arrA, (void*)aA, sizeof(int)*uiSizeA);    memcpy((void*)arrB, (void*)aB, sizeof(int)*uiSizeB);     cout << "\nArray A: ";    for (int i = 0; i < uiSizeA; i++) {        cout << arrA[i] << " ";    }    cout << "\nArray B: ";    for (int i = 0; i < uiSizeB; i++) {        cout << arrB[i] << " ";    }    cout << endl;}  CCombination::~CCombination(){    delete [] arrA, arrB;} void CCombination::Combine() {    if (!orgQue.empty()) {        cout << "Combined already!" << endl;        return;    }     unsigned int iIdxA = 0, iIdxB = 0;     deque <Element> arrangedQue;    arrangedQue.push_back(Element(arrA[iIdxA], true));    iIdxA++;     while (arrB[iIdxB] < arrangedQue.front().value) {        iIdxB++;    }     while (iIdxA < uiSizeA) {        if (iIdxB < uiSizeB && arrB[iIdxB] < arrA[iIdxA]) {            arrangedQue.push_back(Element(arrB[iIdxB], false));            iIdxB++;        }        else {            arrangedQue.push_back(Element(arrA[iIdxA], true));            iIdxA++;        }    }     while (iIdxB < uiSizeB) {        arrangedQue.push_back(Element(arrB[iIdxB], false));        iIdxB++;    }     deque <Element> tmpQue = orgQue = arrangedQue;    cout << "Combined array: ";    while (!tmpQue.empty()) {        cout << tmpQue.front().value << "-" << (tmpQue.front().isArrayA ? "A " : "B ");        tmpQue.pop_front();    }    cout << endl;} void CCombination::PrintResult() {    if (orgQue.empty()) {        cout << "Combine first!" << endl;        return;    }     int iArrangedQueSize = 0;    int iArrangedQueCnt = 0;    int iResQueSize = 0;    int iResQueCnt = 0;    int iResPairs = 0;    bool bFoundFirstB = false;     deque <Element> tmpQue, arrangedQue;    arrangedQue = orgQue;     cout << "Result: \n";    while (1) {        // Create resultQue        iArrangedQueCnt = 0;        iArrangedQueSize = arrangedQue.size();        bFoundFirstB = false;         //cout << iArrangedQueSize << endl;        if (iArrangedQueSize < 2) break;         tmpQue = arrangedQue;        if (false == tmpQue.front().isArrayA) {            iArrangedQueCnt = 0;            orgQue.pop_front();            arrangedQue = orgQue;            continue;        }         iResQueCnt = 0;        while (1) {            if (iArrangedQueCnt == iArrangedQueSize) break;             if (true == tmpQue.front().isArrayA) {                if (true == orgResQue.empty() || iResQueCnt % 2 == 0) {                    orgResQue.push_back(tmpQue.front().value);                    iResQueCnt++;                }                else {                }            }            else {                if (iResQueCnt % 2 == 1 && tmpQue.front().isFirstB) {                    orgResQue.push_back(tmpQue.front().value);                    iResQueCnt++;                    if (false == bFoundFirstB) {                        arrangedQue.at(iArrangedQueCnt).isFirstB = false;                        bFoundFirstB = true;                    }                }                else {                }            }            tmpQue.pop_front();            iArrangedQueCnt++;        }         if (false == arrangedQue.back().isFirstB) {            orgQue.pop_front();            arrangedQue = orgQue;        }         // Display resultQue        iResQueSize = orgResQue.size();        iResPairs = iResQueSize / 2;         deque <int> tmpResQue = orgResQue;        for (int i = 0; i < iResPairs; i++) {            for (int j = 0; j < i + 1; j++) {                cout << tmpResQue.at(2 * j) << " " << tmpResQue.at(2 * j + 1) << " ";            }            cout << endl;        }         orgResQue.clear();    }}  int main(){    int arrA[] = { 10, 15, 25 };    int arrB[] = { 1, 5, 20, 30 };     CCombination MyCombination(3, arrA, 4, arrB);    MyCombination.Combine();    MyCombination.Combine();    MyCombination.PrintResult();     cout << "\n END " << endl;     getchar();    return 0;}