数据结构(C语言版) 串、数组和广义表 算法设计Demo5

设二维数组a[1…m, 1…n] 含有m*n 个整数。
① 写一个算法判断a中所有元素是否互不相同?输出相关信息(yes/no);
② 试分析算法的时间复杂度。

①[题目分析]

判断二维数组中元素是否互不相同,只有逐个比较,找到一对相等的元素,就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次?在当前行,每个元素要同本行后面的元素比较一次(下面第一个循环控制变量p的for循环),然后同第i+1行及以后各行元素比较一次,这就是循环控制变量k和p的二层for循环。

[算法描述]

int JudgEqual(ing a[m][n],int m,n) {
 //判断二维数组中所有元素是否互不相同,如是,返回1;否则,返回0。
for(i=0;i<m;i++)
	for(j=0;j<n-1;j++){
		for(p=j+1;p<n;p++) //和同行其它元素比较
			if(a[i][j]==a[i][p]){
				cout<<"no";
				return(0);
			}
//只要有一个相同的,就结论不是互不相同
    for(k=i+1;k<m;k++)  //和第i+1行及以后元素比较
		for(p=0;p<n;p++)
			if(a[i][j]==a[k][p]){
				cout<<"no";
				return(0);
			}             
}// for(j=0;j<n-1;j++)
	cout<<"yes"; 
	return(1);   //元素互不相同
}//算法JudgEqual结束

② 二维数组中的每一个元素同其它元素都比较一次,数组*mn个元素,第1个元素同其它mn-1个元素比较,第2个元素同其它mn-2 个元素比较,……,第mn-1个元素同最后一个元素(mn)比较一次,所以在元素互不相等时总的比较次数为 (mn-1)+(mn-2)+…+2+1=(mn)(mn-1)/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在(mn-1)个位置上均可能相同,这时的平均比较次数约为(mn)(mn-1)/4,总的时间复杂度是O(n4)。

上一篇:【Warrior刷题笔记】1765.地图中的最高点 【多源广度优先遍历】详细注释简单易懂


下一篇:CF979D Kuro and GCD and XOR and SUM