每日一题 鞍点

发表于 更新于 分类于 本文字数： 543 阅读时长 ≈ 2 分钟

每日一题

公众号新开了个栏目, 叫大概每日一题.

那么问题来了, 为啥叫大概每日一题呢?

鸽子表情包

今天的题

题目描述:

1
找出具有m行n列二维数组Array的“鞍点”，即该位置上的元素在该行上最大，在该列上最小，其中1<=m,n<=10。

输入:

1
第一行有两个数m和n，下面有m行，每行有n个数。

输出:

1
Array[i][j]=x

做题思路

这道题的思路还是比较清晰的: 枚举每一行, 寻找这一行里最大的数在第几列, 寻找那一列最小的数, 看看这一行最大的数是不是这一列最小的数.

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
输入m,n
循环i从0到m-1
    循环j从0到n-1
        读入data[i][j]

循环i从0到m-1
    max=data[i][0]
    pos=0
    循环j从0到n-1
        如果data[i][j] 大于 max
            更新max与pos
    
    flag = 1
    循环j从0到n-1
        如果data[j][pos]小于max
            flag = 0
    如果flag=1 说明data[i][pos]是鞍点
        输出,退出程序
输出none

注意点

在找数组的最小值的时候有两种实现方式:

1
2
3
4
5
6
7
8
int min = 0x70000000;
int pos = -1;
for(int i = 0; i < n;++ i){
    if(min < data[i]){
        min = data[i];
        pos = i;
    }
}

与

1
2
3
4
5
6
7
8
int min = data[0];
int pos = 0;
for(int i = 1; i < n;++ i){
    if(min < data[i]){
        min = data[i];
        pos = i;
    }
}

第一种方式将min设为极大值(或将max设为极小值), 第二种方式奖min设为数组第一项的值.

这两种方式都是正确的, 要注意的就是

  1. 使用第一种方式时设置的极大值一定要很大.
    1. int所能存储的最大值是0x7fffffff, 所以对于以上情况把min设置为0x7ffffff是安全的.
    2. 对于要比较min+data[i]和data[i]的大小的时候, min的初值应设置为int所能存储的最大值的一半, 以保证min+data[i]仍在int范围内. 对于这种情况, 0x3f3f3f3f是一个安全的值.
  2. 使用第二种方式一定要把pos变量初始化为0