两种方法：求矩阵的马鞍点_gyeve

http://blog.sina.com.cn/u/2182902627

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

两种方法：求矩阵的马鞍点

(2011-12-07 15:42:47)

标签：

马鞍点

时间复杂度

o(n3)

o(n)

---0(n2)

杂谈

分类：算法

题目：主要的任务是遍历二维数组，找出数组中行最小列最大的元素，称为马鞍点。
思路一：针对二维数组的每一个元素对它的同行同列都进行判断，如果是则将flag设为1并且输出，否则设为0；
时间复杂度：o(n^3)
代码：
#include<stdio.h>
#define M 20
int main()
{
    int                                data[M][M];
    int                                row, col, inx, iny, min;
    int                                flag = 1;
    int                                i,j;
    int                                count=0;
    printf("please input the col and row\n");
    scanf("%d%d",&row, &col);
    getchar();//接收‘\n’
    printf("please input the memeber of \n");
    for(inx = 0; inx < row; inx++)
        for(iny = 0; iny < col; iny++)
                scanf("%d",&data[inx][iny]);//输入数组的元素
   for(inx = 0; inx < row; inx++)
        for(iny =0; iny < col; iny++){//对每一个二维元素进行判断
            for(i=0; i < col; i++)
                if(data[inx][iny]>data[inx][i])
                    flag = 0;//利用flag进行标志
             for(i=0;i<row&&flag;i++)
                if(data[inx][iny]<data[i][iny])
                    flag = 0;
            if(flag==1){
                   printf("%d: [%d][%d]; \n",data[inx][iny],inx,iny);
               count++;
            }
            flag =1;}
   printf("gong you %d\n",count);
   return 0;
}
思路二：根据 ‘空间复杂度换时间复杂度’ 的思想，多增加了一个一维数组。对于马鞍点来讲，相等的值是一种特例，例如：1 1 1，因此多申请一个数组用于记录每行的最小是位置，下次直接根据位置进行新的判断。
                         1 1 1
时间复杂度：最好是 o(n)----------最坏：o(n^2)
代码：
#include<stdio.h>
#define M 20

int main()
{
    int                                data[M][M];
    int                             count[M]={0};
    int                                row, col, inx, iny,i=0;
    int                                cnt=0;
    printf("please input the col and row\n");
    scanf("%d%d",&row, &col);

    getchar();
    printf("please input the memeber of \n");
    for(inx = 0; inx < row; inx++)
        for(iny = 0; iny < col; iny++)
                scanf("%d",&data[inx][iny]);
    for(inx = 0; inx < row; inx++)
        {
            i = 1;
            count[1]=0;
            count[0] = 1;//记录一行满足条件的个数
            for(iny =1; iny < col; iny++)
                if(data[inx][count[1]] > data[inx][iny])
                {
                    i = 1;
                    count[0]=1;
                    count[1]=iny;//记录行中较小的点的位置。
                }
                 else if(data[inx][count[1]]==data[inx][iny])//处理行中有相等的数据
                {
                    count[++i]=iny;
                    count[0]++;
                }
            // printf("count %d %d %d %d\n",count[0],count[1],count[2],count[3]);
            i =1;
            while(count[0]>0){
                for(iny = 0; iny < row && data[inx][count[i]]>=data[iny][count[i]]; iny++)
                             ;
                if(iny >= row)
                        printf("%d: [%d][%d]\n",data[inx][count[i]],inx,count[i]);
                i++;
                count[0]--;
                }
        }

    printf("\n");
    return 0;
}

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：进程管理

后一篇：最大子段和

新浪BLOG意见反馈留言板　欢迎批评指正

两种方法 ： 求矩阵的马鞍点

马鞍点

时间复杂度

o(n3)

o(n)

---0(n2)

杂谈

两种方法：求矩阵的马鞍点