一个二维数组，找两个数使其和为最大的，要求这两个数不同行不同列

Question

时间要求n2，。n为二维数组一维的长度

Answer 1

说个简单的方法：

数组按照大小排序，排序的同时记录下行号和列号，如果快速排序，时间复杂度log2(n)*n；

遍历排好顺序的数组，两两求和，同行或同列的就跳过，这个过程要遍历(n-1)+(n-2)+...+3+2次，就算时间复杂度为n2吧；

再对结果遍历一次，取最大值，时间复杂度为n；

三步加起来，忽略非主要项，时间复杂度是n2

Answer 2

给个思路：

从行或者列开始都可以，选择元素数量少的，假设是行，然后遍历第一行找到最大的那个值记为a1，次大的记为a11，同时记下列号c1，c11

再遍历第二行，找出最大的记为a2，次大的记为a22，同时记下列号c2，c22

如果c1等于c2（即同列），比较a1 + a22和a2 + a11，保留值最大的组合

如果c1不等于c2（不同列），则保留a1，a2，淘汰a11和a22

继续遍历，并以此类推，只保存两个最大的且列号不同的值，如果列号相同则取最大值组合，这样就可以保证最后取得的是不同列不同行的和最大的两个值

    复杂度应该是两个维度元素的积

仅供参考

Answer 3

#include<stdio.h>
int main()
{
int length[5][5] =
{
{0,1,3,6,8},
{2,6,10,3,14},
{5,6,9,4,8},
{11,15,0,19,3},
{6,18,11,2,2},
};//问题很简单啊，只要找出这个5*5的二维数组中第一大和第二大的数就ok
int NO1,NO2,a,b;
for(int i=0; i<5; i++)
for (int j=0; j<5; j++)
{
a = length[i][j];
b = length[i][j];
b<a;
if(NO1<a)
{
NO1=a;//得到最大的元素
printf("NO1 = %d\n",NO1);
scanf("i = %d j = %d\n",i,j);
}
if(NO2<b)
{
NO2=b;//得到第二大的元素
printf("NO2 = %d\n",NO2);
scanf("i = %d j = %d\n",i,j);
}
}
scanf("NO1 = %d\n",NO1);
scanf("NO2 = %d\n",NO2);
}追问

你 想的太简单了。如果最大和第二大只要在相同行或者相同列就不满足。你这个例子又不能说明全部。

Answer 4

1另开个数组记录数据数组中每个元素的位置(行号，列号)
2将数组中的数据进行排序，在移动数据的同时位置数组也进行相应移动
3选取最大值
4选取最大值后面的次大值
5比较行列号是否满足条件，满足则得到结果
6不满足再去找下一个次大的值进行5追问

把每个数组全排序显然不可能。数组元素都n^2个了。排序的时间复杂度不满足。

追答

寻找最大值，找到后将其行列值记录，将此值赋值成最小值

找最大值，找到后看其行列是否满足条件，满足则完成计算

不满足，将新找到的值赋值成最小值，重复2

以上是破坏数组数据的方法，如果不想破坏需要新开个数组记录顺序找到的最大值以便比较时排除。

追问

如果数组中最大值10，次大9,9，7，其中9两个9与10在同行或者同列，且两个9不同行和同列。这样按照你的方法得到的是10+7 = 17，而事实上应该是9+9 = 18

追答

在第1次查找时会找到一个9，记录它的位置到xy[N][2],N可定义成行或列号最大值加1，定义n，赋值1，即找到一个最大数

接着查找时排除位置从行xy[0][0]列xy[0][1]到xy[n-1][0],xy[n-1][1]位置上的数据，找出最大值并记录位置到xy[n][0],xy[n][1]，n自加1

判断找到的最大值位置与第1个是否同行同列，否则找到，跳出查找循环

否则返回步骤2继续查找