当前位置:编程学习 > C/C++ >>

算法设计:有n个数,范围是从1到n,且只有唯一的两个数相同,如何最快的求相同的这个数值?

为了方便问题描述,假设n = 10,即数组a[10]里有10个数,范围是从1到10,且里面只有两个数的值是相同的。如何求这个相同的数值。

常规思路:

1,先冒泡排序,然后用while循环找出这个相同的数值

2,直接用冒泡的思路,i从0到n-2,j = i+1,依次比,找出相同的数值。

上述复杂度都太高,而且没有充分利用到这里面的特殊条件:有且只有两个值是相同的。

事实上,可以对这个数组a[10]求和 = sum1,然后对从1到10进行求和 = sum2,然后求abs(sum1 - sum2),用这个数组的上界,这里是10 - abs(sum1 - sum2)得到的数值就是那个相同的数值。跟上面一次一次循环遍历相比,这里只是进行两次求和,然后做差,用上界值一减就得到了。

测试程序如下:

[cpp] 
<span style="font-size:18px;">#include <stdio.h> 
 
/*求数组里面n个元素的和*/ 
int getSum1(int a[], int n) 

    int sum = 0; 
    int i; 
    for(i=0; i<n; i++) 
        sum+=a[i]; 
    return sum; 

 
/*求从a到b连续b-a+1个数之和*/ 
int getSum2(int a, int b) 

    int sum = 0; 
    int i; 
    for(i = a; i<=b; i++) 
        sum = sum+i; 
    return sum; 

 
/*求两个数做差后的绝对值*/ 
int getAbs(int a, int b) 

    return a-b>0? a-b:b-a; 

 
int main() 

     
    int a[10] = {1, 10, 3, 4, 5, 6, 7, 8, 9, 10}; 
    int sum1 = getSum2(1, 10); 
    int sum2 = getSum1(a, 10); 
    int ret = 10 -getAbs(sum1, sum2); 
    printf("sum1 = %d, sum2 = %d, ret = %d\n", sum1, sum2, ret); 
    return 0; 
}</span> 

 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,