c++给定n*m矩阵A，设计算法判定x是否在A中，要求时间复杂度为O(m+n)

好的，针对您的问题，我会给出如下算法：

1. 从矩阵A的左下角元素开始查找；
2. 如果当前元素小于 x，则向右移动一格；
3. 如果当前元素大于 x，则向上移动一格；
4. 如果当前元素等于 x，则返回 true；
5. 如果已经达到矩阵A的右上角，仍未找到 x，则返回 false；

该算法的时间复杂度为 O(m+n)，符合您的要求。

相关问题

用c++编写程序，把M*N矩阵A加上矩阵A的转置，存放在矩阵B中

下面是用 C 语言编写的程序，实现将 M*N 矩阵 A 加上矩阵 A 的转置，存放在矩阵 B 中的操作：

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

int main(){
    int m,n,i,j;
    printf("请输入矩阵的行数和列数: ");
    scanf("%d%d",&m,&n);
    int **A,**B;
    A=(int **)malloc(m*sizeof(int*));
    B=(int **)malloc(m*sizeof(int*));
    for(i=0;i<m;i++){
        A[i]=(int *)malloc(n*sizeof(int));
        B[i]=(int *)malloc(m*sizeof(int));
    }
    printf("请输入矩阵A: ");
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            scanf("%d",&A[i][j]);
        }
    }
    for(i=0;i<m;i++){
        for(j=0;j<m;j++){
            B[i][j]=A[i][j]+A[j][i];
        }
    }
    printf("矩阵B为:\n");
    for(i=0;i<m;i++){
        for(j=0;j<m;j++){
            printf("%d ",B[i][j]);
        }
        printf("\n");
    }
    for(i=0;i<m;i++){
        free(A[i]);
        free(B[i]);
    }
    free(A);
    free(B);
    return 0;
}

程序首先通过输入的行数和列数，动态分配了两个指针数组 A 和 B，分别表示矩阵 A 和矩阵 B。接着，程序通过循环输入矩阵 A 中的每个元素。然后，程序通过两个循环遍历矩阵 A，将 A 矩阵加上其转置，存放在 B 矩阵中。最后，程序输出矩阵 B 中的每个元素，释放内存并结束程序。

需要注意的是，这里假设输入的矩阵 A 是一个对称矩阵（即 A 矩阵等于其转置），否则程序需要进行额外的计算。

用c++写时间复杂度为O(n)的查找中位数算法

可以使用快速选择算法来实现时间复杂度为O(n)的查找中位数。具体步骤如下：

1. 选取数组中任意一个数作为pivot。

2. 将数组中小于pivot的数放在数组左边，大于pivot的数放在数组右边，pivot放在中间。

3. 比较pivot的索引与中位数的索引，如果相等，返回pivot；如果pivot的索引大于中位数的索引，则在pivot左边递归查找中位数；如果pivot的索引小于中位数的索引，则在pivot右边递归查找中位数。

4. 重复步骤1-3，直到找到中位数为止。

需要注意的是，如果数组长度为偶数，则中位数为中间两个数的平均值。