2011年专业408算法题

0 结果

1 题目

2 思路

2.1 思路1（暴力解：排序）

将两个数组放入新的数组用快速排序，输出排序后数组中第n个元素。

#include <cstdio>
#include <cstdlib>
#include <algorithm>

//快排
void Qsort(int A[], int L, int R){
    if(L >= R) return;
    int pivot, i = L, j = R;
    std::swap(A[L], A[rand()%(R - L + 1) + L]);
    pivot = A[L];
    while(i < j){
        while(i < j && A[j] > pivot) j--;
        while(i < j && A[i] <= pivot) i++;
        if(i < j) std::swap(A[i], A[j]);
    }
    std::swap(A[L], A[i]);
    Qsort(A, L, i - 1);
    Qsort(A, i + 1, R);
}

void ans(int A[], int B[], int n){
    int* C = (int*) malloc(sizeof (int) * 2 * n);
    for(int i = 0;i < n;i++){//合并两个数组
        C[i] = A[i];
        C[n + i] = B[i];
    }
    Qsort(C, 0, 2*n - 1);
    printf("%d", C[n - 1]);//输出中位数
}

int main(){
    int A[] = {11, 13, 15,17, 19};
    int B[] = {2, 4, 6, 8, 20};
    ans(A, B, sizeof(A)/sizeof(A[0]));

    return  0;
}

时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度： O ( n ) O(n) O(n)

2.2 思路2（较优解：归并合并数组）

对数组A和B使用归并的方式合并到新数组C中得到升序数组。

归并的方式为：给数组A和B的下标设置变量i和j，初始为0，每次比较A[i]和B[j]，数组C的下一个空位保存较小的那个元素，并使对应的数组下标后移，直到一个数组遍历完，把另一个数组剩下的元素依次保存到数组C中。

#include <cstdio>
#include <cstdlib>


void ans(int A[], int B[], int n){
    int* C = (int*) malloc(sizeof (int) * n * 2);
    int i = 0, j = 0, index = 0;
    while(i < n && j < n){//归并合并
        if(A[i] < B[j]) C[index++] = A[i++];
        else C[index++] = B[j++];
    }
    while(i < n) C[index++] = A[i++];//处理剩余的元素
    while(j < n) C[index++] = B[j++];
    printf("%d", C[n - 1]);
}

int main(){
    int A[] = {11, 13, 15,17, 19};
    int B[] = {2, 4, 6, 8, 20};
    ans(A, B, sizeof(A)/sizeof(A[0]));

    return  0;
}

时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( n ) O(n) O(n)

2.3 思路3（较优解：数组指针后移）

在上一种思路的基础上，不保存新的数组C。让数组A和B比较n-1次，到第n次时，此时A[i]和B[j]中较小的一个就会放在数组C的第n个位置上，即中位数。

#include <cstdio>
#include <algorithm>

void ans(int A[], int B[], int n){
    int i = 0, j = 0;
    for (int k = 1; k < n; ++k) {
        if(A[i] < B[j]) i++;
        else j++;
    }
    printf("%d", std::min(A[i], B[j]));
}

int main(){
    int A[] = {11, 13, 15,17, 19};
    int B[] = {2, 4, 6, 8, 20};
    ans(A, B, sizeof(A)/sizeof(A[0]));

    return  0;
}

时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( 1 ) O(1) O(1)

2.4 思路4（最优解：两个数组的折半查找）

对数组A、B进行折半查找，设L1、R1为数组A的左右查找边界，L2，R2位数组B的左右查找边界。数组 A [ L 1 ∼ R 1 ] A[L_1 \sim R_1] A[L1​∼R1​]和 B [ L 2 ∼ R 2 ] B[L_2 \sim R_2] B[L2​∼R2​]的中位数，设为a和b，求序列A、B的中位数过程如下：

• 1，若a < b，则舍弃序列A中较小的一半 A [ L 1 ∼ L m i d − 1 ] A[L_1 \sim L_{mid- 1}] A[L1​∼Lmid−1​]，同时舍弃序列B中较大的一半 B [ L m i d + 1 ∼ L R 2 ] B[L_{mid+1} \sim L_{R2}] B[Lmid+1​∼LR2​] ;
• 2，若a >=b，则舍弃序列A中较大的一半 A [ L m i d + 1 ∼ L R 1 ] A[L_{mid+1} \sim L_{R1}] A[Lmid+1​∼LR1​]，同时舍弃序列B中较小的一半 B [ L 2 ∼ L m i d − 1 ] B[L_2 \sim L_{mid- 1}] B[L2​∼Lmid−1​] ;
• 3,重复过程1，2，且保证序列A、B中的元素个数相同，如果不同，则从长的数组中舍弃一个（因为mid为向下取整，舍弃较小的那个），直到两个序列均只含一个元素时为止，较小者则为所求中位数。

例子：
序列A：11，3，15，17，19
序列B：2，4，6，8，20

#include <cstdio>
#include <algorithm>

void ans(int A[], int B[], int n){
    int mid1, mid2, L1 =  0, L2 = 0, R1 = n- 1, R2 = n- 1;
    while (L1 < R1){
        mid1 = (L1 + R1)/2;
        mid2 = (L2 + R2)/2;
        if(A[mid1] < B[mid2]){
            L1 = mid1;
            R2 = mid2;
            if(R1 - L1 != R2 - L2)
                L1++;
        }else{
            R1 = mid1;
            L2 = mid2;
            if(R1 - L1 != R2 - L2)
                L2++;
        }
    }
    printf("%d", std::min(A[L1], B[L2]));
}

int main(){
    int A[] = {11, 13, 15,17, 19};
    int B[] = {2, 4, 6, 8, 20};
    ans(A, B, sizeof(A)/sizeof(A[0]));

    return  0;
}

附录

408历年真题算法题解析