百度实习生笔试题数组内Merge解决办法

百度实习生笔试题数组内Merge
题目：

算法和程序设计二：数组al[0...mid-1]和al[mid...num-1]两个部分都已经分别排好序。要求合并使得整个数组al有序。请给出合并merge的代码。要求空间复杂度为O(1)。

我的想法的时间复杂度可能到了o(n^2)了，所以想求教大家的思路。

------解决方案--------------------
我的想法是：定义两个游标，分别指向两段的未处理的数据，然后根据游标来插入数据，并且将第二段之前的数据进行后移一格。估计时间复杂度也很高。
------解决方案--------------------

探讨
C/C++ code

i = 0;
j = mid;
while (j < num){
if (a[i] < a[j])
i++;
else {
temp = a[j];
for (int k = j; k >= i; --k)
a[k] = a[k-1];
a[i] =……

------解决方案--------------------

探讨

引用:
C/C++ code

i = 0;
j = mid;
while (j < num){
if (a[i] < a[j])
i++;
else {
temp = a[j];
for (int k = j; k >= i; --k)
a[k] = a[k-1];
……

------解决方案--------------------

C/C++ code


void mergeArray(int a[], int first, int mid ,int last)
{
    int i, j = mid +1;
    int k, flag = 0;

    while ( a[j] < a[j-1] && j <= last )
    {
        k = flag;
        for ( i = j-1; i >= k ; i--)
            if ( a[i] > a[i+1] )
            {
                Swap( a[i], a[i+1] );
                flag = i;
            }
        j ++;
    }
}

------解决方案--------------------
很简单，前半段的小那么不用操作，后半段的小，就把后半段和前半段交换，然后后半段做一个插入排序（因为交换前后半段<前半段，所以交换后需向后做插入排序）。

------解决方案--------------------

探讨
题目：

算法和程序设计二：数组al[0...mid-1]和al[mid...num-1]两个部分都已经分别排好序。要求合并使得整个数组al有序。请给出合并merge的代码。要求空间复杂度为O(1)。

我的想法的时间复杂度可能到了o(n^2)了，所以想求教大家的思路。

------解决方案--------------------

探讨

算法复杂度最低应该是O(n)

------解决方案--------------------

C/C++ code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int lower_bound(int *arr, int begin, int end, int target) {
    while (begin <= end) {
        int middle = begin + (end - begin) / 2;
        if (target <= arr[middle]) {
            end = middle - 1;
        } else {
            begin = middle + 1;
        }
    }

    return end + 1;
}

int merge(int *arr, int num) {
    if (arr == NULL) {
        return -1;
    } 

    if (num <= 1) {
        return 0;
    }

    int l_begin = 0, l_end = (num / 2) - 1;
    int r_begin = l_end + 1, r_end = num -1;
    
    while (l_begin <= l_end) {
        if (arr[l_begin] > arr[r_begin]) {
            int temp = arr[l_begin];
            arr[l_begin] = arr[r_begin];
            /* 慢速版
            int ndx = r_begin + 1;            
            while (ndx <= r_end && temp > arr[ndx]) {
                arr[ndx - 1] = arr[ndx];
                ++ ndx;
            }

            arr[ndx - 1] = temp;
            */ 

            /* 二分版 */
            if (r_end - r_begin + 1 > 1) {
                int ndx = lower_bound(arr, r_begin + 1, num - 1, temp);
                if (ndx == r_begin + 1) {
                    arr[r_begin] = temp;
                } else {
                    memmove(arr + r_begin, arr + r_begin + 1, 
                        sizeof(int) * (ndx - r_begin - 1));
                    arr[ndx - 1] = temp;
                }
            } else {
                arr[r_begin] = temp;
            }
        }

        ++ l_begin;
    }

    return 0;
}

int main(int argc, char* const argv[]) {
    int arr[] = {1, 4, 4, 5, 6, 6, 1, 2, 2, 3, 3, 4, 5};
    int ret = merge(arr, sizeof(arr) / sizeof(arr[0]));
    
    if (!ret) {
        int i = 0;
        
        for ( ; i < sizeof(arr) / sizeof(arr[0]); ++ i ) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    }

    return 0;
}

百度实习生笔试题 数组内Merge解决办法

相关推荐

百度实习生笔试题数组内Merge解决办法