Từ 1 tới 3 trên tổng số 3 kết quả

Đề tài: Dãy sắp xếp tạo ra từ hai dãy sắp xếp (Microsoft)

  1. #1
    Ngày gia nhập
    02 2017
    Bài viết
    2

    Mặc định Dãy sắp xếp tạo ra từ hai dãy sắp xếp (Microsoft)

    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!

  2. #2
    Ngày gia nhập
    04 2018
    Bài viết
    3

    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

  3. #3
    Ngày gia nhập
    04 2018
    Bài viết
    3

    Đây là code mình viết bạn có thể tham khảo.
    C++ Code:
    1. #include "stdafx.h"
    2.  
    3. #include <deque>
    4. #include <iostream>
    5.  
    6. using namespace std;
    7.  
    8. typedef struct Elem {
    9.     Elem(int val, bool isA) : value(val), isArrayA(isA), isFirstB(true) {}
    10.     int value;
    11.     bool isArrayA;
    12.     bool isFirstB;
    13. } Element;
    14.  
    15. class CCombination {
    16. public:
    17.     CCombination(unsigned int sizeA, int *a, unsigned int sizeB, int *b);
    18.     ~CCombination();
    19.  
    20.     void Combine();
    21.     void PrintResult();
    22.  
    23. private:
    24.     int *arrA, *arrB;
    25.     unsigned int uiSizeA, uiSizeB;
    26.     deque <Element> orgQue;
    27.     deque <int> orgResQue;
    28. };
    29.  
    30. CCombination::CCombination(unsigned int sizeA, int *aA, unsigned int sizeB, int *aB)
    31.     : uiSizeA(sizeA), uiSizeB(sizeB)
    32. {
    33.     arrA = new int[uiSizeA];
    34.     arrB = new int[uiSizeB];
    35.     memcpy((void*)arrA, (void*)aA, sizeof(int)*uiSizeA);
    36.     memcpy((void*)arrB, (void*)aB, sizeof(int)*uiSizeB);
    37.  
    38.     cout << "\nArray A: ";
    39.     for (int i = 0; i < uiSizeA; i++) {
    40.         cout << arrA[i] << " ";
    41.     }
    42.     cout << "\nArray B: ";
    43.     for (int i = 0; i < uiSizeB; i++) {
    44.         cout << arrB[i] << " ";
    45.     }
    46.     cout << endl;
    47. }
    48.  
    49.  
    50. CCombination::~CCombination()
    51. {
    52.     delete [] arrA, arrB;
    53. }
    54.  
    55. void CCombination::Combine()
    56. {
    57.     if (!orgQue.empty()) {
    58.         cout << "Combined already!" << endl;
    59.         return;
    60.     }
    61.  
    62.     unsigned int iIdxA = 0, iIdxB = 0;
    63.  
    64.     deque <Element> arrangedQue;
    65.     arrangedQue.push_back(Element(arrA[iIdxA], true));
    66.     iIdxA++;
    67.  
    68.     while (arrB[iIdxB] < arrangedQue.front().value) {
    69.         iIdxB++;
    70.     }
    71.  
    72.     while (iIdxA < uiSizeA) {
    73.         if (iIdxB < uiSizeB && arrB[iIdxB] < arrA[iIdxA]) {
    74.             arrangedQue.push_back(Element(arrB[iIdxB], false));
    75.             iIdxB++;
    76.         }
    77.         else {
    78.             arrangedQue.push_back(Element(arrA[iIdxA], true));
    79.             iIdxA++;
    80.         }
    81.     }
    82.  
    83.     while (iIdxB < uiSizeB) {
    84.         arrangedQue.push_back(Element(arrB[iIdxB], false));
    85.         iIdxB++;
    86.     }
    87.  
    88.     deque <Element> tmpQue = orgQue = arrangedQue;
    89.     cout << "Combined array: ";
    90.     while (!tmpQue.empty()) {
    91.         cout << tmpQue.front().value << "-" << (tmpQue.front().isArrayA ? "A " : "B ");
    92.         tmpQue.pop_front();
    93.     }
    94.     cout << endl;
    95. }
    96.  
    97. void CCombination::PrintResult()
    98. {
    99.     if (orgQue.empty()) {
    100.         cout << "Combine first!" << endl;
    101.         return;
    102.     }
    103.  
    104.     int iArrangedQueSize = 0;
    105.     int iArrangedQueCnt = 0;
    106.     int iResQueSize = 0;
    107.     int iResQueCnt = 0;
    108.     int iResPairs = 0;
    109.     bool bFoundFirstB = false;
    110.  
    111.     deque <Element> tmpQue, arrangedQue;
    112.     arrangedQue = orgQue;
    113.  
    114.     cout << "Result: \n";
    115.     while (1) {
    116.         // Create resultQue
    117.         iArrangedQueCnt = 0;
    118.         iArrangedQueSize = arrangedQue.size();
    119.         bFoundFirstB = false;
    120.  
    121.         //cout << iArrangedQueSize << endl;
    122.         if (iArrangedQueSize < 2) break;
    123.  
    124.         tmpQue = arrangedQue;
    125.         if (false == tmpQue.front().isArrayA) {
    126.             iArrangedQueCnt = 0;
    127.             orgQue.pop_front();
    128.             arrangedQue = orgQue;
    129.             continue;
    130.         }
    131.  
    132.         iResQueCnt = 0;
    133.         while (1) {
    134.             if (iArrangedQueCnt == iArrangedQueSize) break;
    135.  
    136.             if (true == tmpQue.front().isArrayA) {
    137.                 if (true == orgResQue.empty() || iResQueCnt % 2 == 0) {
    138.                     orgResQue.push_back(tmpQue.front().value);
    139.                     iResQueCnt++;
    140.                 }
    141.                 else {
    142.                 }
    143.             }
    144.             else {
    145.                 if (iResQueCnt % 2 == 1 && tmpQue.front().isFirstB) {
    146.                     orgResQue.push_back(tmpQue.front().value);
    147.                     iResQueCnt++;
    148.                     if (false == bFoundFirstB) {
    149.                         arrangedQue.at(iArrangedQueCnt).isFirstB = false;
    150.                         bFoundFirstB = true;
    151.                     }
    152.                 }
    153.                 else {
    154.                 }
    155.             }
    156.             tmpQue.pop_front();
    157.             iArrangedQueCnt++;
    158.         }
    159.  
    160.         if (false == arrangedQue.back().isFirstB) {
    161.             orgQue.pop_front();
    162.             arrangedQue = orgQue;
    163.         }
    164.  
    165.         // Display resultQue
    166.         iResQueSize = orgResQue.size();
    167.         iResPairs = iResQueSize / 2;
    168.  
    169.         deque <int> tmpResQue = orgResQue;
    170.         for (int i = 0; i < iResPairs; i++) {
    171.             for (int j = 0; j < i + 1; j++) {
    172.                 cout << tmpResQue.at(2 * j) << " " << tmpResQue.at(2 * j + 1) << " ";
    173.             }
    174.             cout << endl;
    175.         }
    176.  
    177.         orgResQue.clear();
    178.     }
    179. }
    180.  
    181.  
    182. int main()
    183. {
    184.     int arrA[] = { 10, 15, 25 };
    185.     int arrB[] = { 1, 5, 20, 30 };
    186.  
    187.     CCombination MyCombination(3, arrA, 4, arrB);
    188.     MyCombination.Combine();
    189.     MyCombination.Combine();
    190.     MyCombination.PrintResult();
    191.  
    192.     cout << "\n END " << endl;
    193.  
    194.     getchar();
    195.     return 0;
    196. }

Tags của đề tài này

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn