itgle.com

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

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

相似考题

1.设任意n个整数存放于数组A(1:n)中,试编写算法,将所有正数排在所有负数前面(要求算法复杂度为0(n))。

2.设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（）A．(i-1)*n+jB．(i-1)*n+j-1C．i*(j-1)D．j*m+i-1

3.设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组中元素A[i][j]在一维数组B中的下标为（)。A．（i-1）n+jB．（i-1）n+j-1C．i（j-1）D．jm+i-1

4.设二维数组A[1..m,1..n](即m行n列)按行存储在数组B[1..m*n]中,则二维数组元素A[i,j]在一维数组B中的下标为()。A.(i-1)*n+jB、(i-1)*n+j-1C.i*(j-1)D、j*m+i-1

参考答案和解析
参考答案：①判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次?在当前行，每个元素要同本行后面的元素比较一次(下面第一个循环控制变量p的for循环)，然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k和p的二层for循环。
　　[算法描述]
　　int JudgEqual(ing a[m][n],int m,n)
　　//判断二维数组中所有元素是否互不相同，如是，返回1;否则，返回0。
　　{for(i=0;i　　for(j=0;j　　{for(p=j+1;p　　if(a[i][j]==a[i][p]) {cout<<“no”; return(0); }
　　//只要有一个相同的，就结论不是互不相同
　　for(k=i+1;k　　for(p=0;p　　if(a[i][j]==a[k][p]) { cout<<“no”; return(0); }
　　}// for(j=0;j　　cout<<“yes”; return(1); //元素互不相同
　　}//算法JudgEqual结束
　　②二维数组中的每一个元素同其它元素都比较一次，数组中共m*n个元素，第1个元素同其它m*n-1个元素比较，第2个元素同其它m*n-2 个元素比较，……，第m*n-1个元素同最后一个元素(m*n)比较一次,所以在元素互不相等时总的比较次数为 (m*n-1)+(m*n-2)+…+2+1=(m*n)(m*n-1)/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在(m*n-1)个位置上均可能相同,这时的平均比较次数约为(m*n)(m*n-1)/4，总的时间复杂度是O(n4)。
更多“设二维数组a[1..m, 1..n] 含有m*n 个整数。 ① 写一个算法判断a中所有元素是否互不相同?输出相关信息(yes／no); ② 试分析算法的时间复杂度。 ”相关问题

  • 第1题：

    设A是含有n个元素的数组，如果元素x在A出现的次数大于n/2，则称x是A的主元素。 （1）如果A中元素是可以排序的，设计一个O（nlogn)时间的算法，判断A中是否存在主元素。 （2）对于（1）中可排序的数组，能否设计一个O（n)时间的算法？ （3）如果A中元素只能进行“是否相等”的测试，但是不能进行排序，设计一个算法判断A中是否存在主元素。


    证明 (1)因为|A|=n，所以|ρ(A)|=2 n ． 所以A上有2 n 个一元关系． (2)因为|A|=n，所以|A×A|=n 2 ，所以有|ρ(A×A)|=2 n 2 ，因此A上有2 n 2 个二元关系．

  • 第2题：

    纸质作业 算法设计：设计求解下列问题的类C语言算法，并分析其最坏情况的时间复杂度及其量级。 （1）在数组A[1..n]中查找值为K的元素，若找到则输出其位置i（1＜=i＜=n)，否则输出0作为标志。 （2）找出数组A[1..n]中元素的最大值和次最大值（本小题以数组元素的比较为标准操作）。


    穷举算法;分解算法;并行算法

  • 第3题：

    设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为（)。

    A．(i-1）*n+j

    B．(i-1）*n+j-1

    C．i*（j-1）

    D．j*m+i-1


    A 此题考查的知识点是顺序存储数组的地址计算。要先计算前i一1行的个数为(i一1)×n，再加上第i行的j个元素即为所求。所以应选A。

  • 第4题：

    设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为（)

    A．（i-1）*n+j

    B．（i-1）*n+j-1

    C．i*（j-1）

    D．j*m+i-1


    A 此题考查的知识点是顺序存储数组的地址计算。要先计算前i一1行的个数为(i一1)×n，再加上第i行的j个元素即为所求。所以应选A。

  • 第5题：

    设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为（)。

    A．（i-1）*n+j

    B．（i-1）*n+j-1

    C．i*（j-1）

    D．j*m+i-1


    A 此题考查的知识点是顺序存储数组的地址计算。要先计算前i一1行的个数为(i一1)×n，再加上第i行的j个元素即为所求。所以应选A。

相关内容