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