华为面试题(8分钟写出代码)

dnd371

难度大， 不过不考虑效率， 可以先整体排序， 然后再平均分到两个数组。   然后根据0-n对等比较，再排！

shevchenln

如果允许O(n^2)的空间复杂度，可以这样做。
1. 计算数组A的和减去数组B的和，得到两数组和的差
2. 用第一个数组A的每一个元素减去数组B中的每一个元素的值，保存在n阶矩阵中，矩阵标号为两个数组的互换标号。
3. 将问题转化为求n阶矩阵和与第一步计算出的差值的最接近的值。这个问题比较容易求解。

算法复杂度为O(n^2)。

shevchenln

回复 449# 路上风声


    这个思路有问题，每次都取差值也不能保证和是最小的。

vbs100

回复 443# lovai

DP算法，dp[j]表示i个数的和为j的方案数，如果用dp额外再保存具体的方案，就容易得出最终的算法。

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. 
   
5. #define MOD     1000
   
6. #define N       10
   
7. 
   
8. int C[N*2];
   
9. int dp[N+1][MOD*N*2];
   
10. 
    
11. int main()
    
12. {
    
13.         int i,j,k,n,sum;
    
14.         while(~scanf("%d",&n)&&n)
    
15.         {
    
16.                 memset(dp,0,sizeof(dp));
    
17.                 for(i=0,sum=0;i<n*2;i++)
    
18.                 {
    
19.                         scanf("%d",&C[i]);
    
20.                         sum+=C[i];
    
21.                 }
    
22.                 dp[0][0]=1;
    
23.                 for(i=0;i<2*n;i++)
    
24.                         for(j=sum/2;j>=C[i];j--)
    
25.                                 for(k=n;k>0;k--)
    
26.                                         if(dp[k-1][j-C[i]])
    
27.                                                 dp[k][j]++;
    
28.                 for(i=sum/2;i>0;i--)
    
29.                         if(dp[n][i])
    
30.                                 break;
    
31.                 printf("%d %d\n",i,sum-i);
    
32.         }
    
33. }
    

复制代码

folklore

我倒， 这个问题这么难么? 这么久没人给出正确的答案？
答案是做一个 m+n的数组， 求平均值e，
然后不就是从m+n个元素中求 m个元素和最接近于e的背包问题了么？

雷男

数组A和数组B，

两个数组的数字进行排序，排序后数组C，和为sum
c[0]放入a[0]，sum = sum-c[0],
如果c[0]>sum则c中剩余元素从大到小依次填充到b中，再剩余元素填充到a中
反之，则将c[1]填充到b[0],sum = sum-b[0]

重复上面的步骤，注意此时应将c[3]填充到b[1]

Sky_47

8分钟...

ANONYMOUS419

PP

zhangbo357

大致思想就是将两个数组a b的差放到另一个数组c，再对c数组求和，再用该和减c数组中的元素，如果减了之后绝对值变小了就将对应位置的a b数组元素交换，直到最后，就这么简单
测试了下 貌似正确

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int main()
   
5. {
   
6.     int a[5] = {6,5,8,4,9};
   
7.     int b[5] = {5,8,5,1,6};
   
8.     int c[5] = {0};
   
9.     int sum1 = 0,sum2 = 0,suma = 0,sumb = 0;
   
10.     int i;
    
11.     for(i = 0;i < 5;i++)
    
12.     {
    
13.         c[i] = a[i]-b[i];
    
14.         sum1 +=c[i];
    
15.     }
    
16.     printf("%d\n",sum1);
    
17.     for( i = 0;i < 5;i++)
    
18.     {
    
19.         sum2 = abs(sum1);
    
20.         if(abs(sum1 - c[i]*2) < sum2)
    
21.         {
    
22.             sum1 -= c[i]*2;
    
23.             
    
24.             a[i] ^= b[i];
    
25.             b[i] ^= a[i];
    
26.             a[i] ^= b[i];
    
27.         }
    
28.         suma += a[i];
    
29.         sumb += b[i];
    
30.         printf("%d %d\n",a[i],b[i]);
    
31.     }
    
32.    
    
33.     printf("%d\n",suma-sumb);
    
34.    
    
35.     return 0;
    
36. }
    

复制代码

zhangbo357

我觉得题目还是有歧义，我理解的是对应位置相交换，而不是任意位置相交换回复 458# zhangbo357