程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 算法設計:有n個數,范圍是從1到n,且只有唯一的兩個數相同,如何最快的求相同的這個數值?

算法設計:有n個數,范圍是從1到n,且只有唯一的兩個數相同,如何最快的求相同的這個數值?

編輯:C++入門知識

為了方便問題描述,假設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> 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved