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

索建伟

//这个可以吗
#include<stdio.h>
#include<math.h>
#define N 3
int main()
{
        int i=0,j=0,k=0,temp;
        int a[N],b[N],c[2*N];
        printf("input %d numbers for a[%d]:\n",N,N);
        for(i=0;i<N;i++){
                scanf("%d",&a[i]);
        }
        printf("input %d numbers for b[%d]:\n",N,N);
        for(i=0;i<N;i++){
                scanf("%d",&b[i]);
        }
        for(i=0;i<N;i++){
                c[2*i]=a[i];
                c[2*i+1]=b[i];
        }

        putchar(10);
        for(i=0;i<(2*N-1);i++)
                for(j=i+1;j<2*N;j++)
                {
                        if(c[i]>c[j])
                        {
                                temp=c[i];
                                c[i]=c[j];
                                c[j]=temp;                               
                        }
                }
        putchar(10);
        int suma=0,sumb=0,abs=0;
        a[0]=c[0];
        b[0]=c[1];
        suma=a[0];
        sumb=b[0];
        for(i=1;i<N;i++){
                if(suma<sumb){
                        b[i]=c[2*i];
                        a[i]=c[2*i+1];
                }
                else{
                        a[i]=c[2*i];
                        b[i]=c[2*i+1];
                }
                suma+=a[i];
                sumb+=b[i];
        }
       
        if(suma<sumb){
                abs=sumb-suma;
                for(i=0;i<N;i++)
                        for(j=0;j<N;j++){
                                if((b[i]>a[j])&&((b[i]-a[j])<abs)){
                                        temp=a[j];
                                        a[j]=b[i];
                                        b[i]=temp;
                                }
                                abs=sumb-suma;
                        }
       
        }
        else{
                abs=suma-sumb;
                for(i=0;i<N;i++)
                        for(j=0;j<N;j++)
                                if( (a[i]>b[j])&&(a[i]-b[j]<abs) ){
                                        temp=b[j];
                                        b[j]=a[i];
                                        a[i]=temp;
                                }
        }
        printf("a      b\n");
        for(i=0;i<N;i++)
                        printf("%-7d%d\n",a[i],b[i]);

        return 0;
}

晓得飞天千秋雪

这是被网上讨论烂了的问题，我也来凑个热闹。

#include <stdio.h>
#include <math.h>
int main(void)
{
   int n = 4;
   int a[4] = {-1, 3, -5, 7};
   int b[4] = {11, 13, 17, -19};
   int i, j, k = 1;
   int d0 = 0, d1, temp;
   for(i=0; i<n; i++) {
       d0 = d0 + a - b;
   }
   while(k > 0) {
       k = 0;
       for(i=0; i<n; i++) {
           for(j=0; j<n; j++) {
               d1 = d0 - 2*(a - b[j]);
               if(abs(d1) < abs(d0)) {
                   temp = a;
                   a = b[j];
                   b[j] = temp;
                   d0 = d1;
                   k = 1;
                   break;
               }
           }
           if(1 == k) {
               break;
           }
       }
   }
   printf("d = %d", d0);
   printf("\na = ");
   for(i=0; i<n; i++) {
       printf("%d ", a);
   }
   printf("\nb = ");
   for(i=0; i<n; i++) {
       printf("%d ", b);
   }
   return 0;
}

http://kan.weibo.com/con/3562687971904001

除美灭日平韩

编码基本都会写，关键是这个算法是什么。。。
谁能把这个算法说清楚了才行啊

Frahm

全排，放到一个数组里a[2n]，问题就是把这个数组均匀分成两个。
写了下，主要有2点，1是必须从后向前选，因为只有最后两个可以保证是分别属于两个数组的。
还有，一个数组满的时候，另一个不用看和是多少，全放进里面，代码大概是

1. int main() {
   
2.         {
   
3.                 static const int n = 10;
   
4.                 int a[2*n];
   
5.                 for(int i = 0; i < 2*n ; ++i) {
   
6.                         a[i] = i;
   
7.                 }
   
8.                 int sum1 = a[2*n-1], sum2 = a[2*n-2]; //记录两个数组当前和
   
9.                 int a1[n], a2[n]; //分完的数组
   
10.                 a1[0] = sum1;
    
11.                 a2[0] = sum2;
    
12.                 int count1 = 1, count2 = 1; //分别记录两个数组当前选中元素个数
    
13.                 for(int i = 2*n - 3; i >= 0; --i) {
    
14.                         if(count1 == n) { //如果数组1满了,后面的全是数组2的
    
15.                                 for(int j = i; j >=0; --j) {
    
16.                                         sum2 += a[j];
    
17.                                         a2[count2++] = a[j];
    
18.                                 }
    
19.                                 break;
    
20.                         } else if(count2 == n) {//如果数组2满了，后面的全是数组1的
    
21.                                 for(int j = i; j >=0; --j) {
    
22.                                         sum1 += a[j];
    
23.                                         a1[count1++] = a[j];
    
24.                                 }
    
25.                                 break;
    
26.                         } else if(sum1 < sum2){//数组1，2都有余位，且sum1 < sum2
    
27.                                 sum1 += a[i];
    
28.                                 a1[count1++] = a[i];
    
29.                         } else { ///数组1，2都有余位，且sum1 >= sum2
    
30.                                 sum2 += a[i];
    
31.                                 a2[count2++] = a[i];
    
32.                         }
    
33.                 }
    
34.                 std::cout << "a1:\n";
    
35.                 for(int i : a1) {
    
36.                         std::cout << i << ' ';
    
37.                 }
    
38.                 std::cout << "\na2:\n";
    
39.                 for(int i : a2) {
    
40.                         std::cout << i << ' ';
    
41.                 }
    
42.                 std::cout << '\n';
    
43. }

复制代码

看看这思路对不对，也没测试过几组数据
注：我这个代码是假设a[2*n]是两个数组合并排序后的，这个代码其实是O(n)的，里面的那层循环是为了免去多余判断

Frahm

Frahm 发表于 2013-04-11 19:51
全排，放到一个数组里a[2n]，问题就是把这个数组均匀分成两个。
写了下，主要有2点，1是必须从后向前选，因 ...

又想了下，果然还是不行，我这个是根据当前状态算出的，而每个数应该被放在哪个数组是需要全局的状态才能决定的。

Frahm

我想这次应该是对的了，之前忽略了负数的问题，还有对比顺序问题，现在下面这个的基本思想是:
假设两个数组都已合并到数组a[2*n], 要把它均匀地分到两个数组里，很容易想到，插入的顺序应该是从对数组和影响最大的那个开始，再依次插入影响小的。因为值可能是负的，那么简单的排序再依次插入就行不通了，因为一个值对整体数组和的影响力不在于它的值本身，而是其绝对值，所以要按原值的绝对值排序。
其次，对于某些特殊情况比如两个数组的和相等时，那么下一个值该放到哪里？如果随意的放，那么很可能导致一个数组在经历多次这种情况后被填满，而后面还有很多数没有参与求和比较，所以我采用的策略是在和相等时，把新值放到元素个数少的那一个里。因为当任一数组满时，剩下的未插入的元素数越少越好(越多则代表越多的数据被浪费，未参与求和比较)

1. 
   
2. bool compare(int lhs, int rhs) {
   
3.         return abs(lhs) > abs(rhs);
   
4. }
   
5. 
   
6. int main() {
   
7.                 static const int n = 4;
   
8.                 //int a[2*n] = {-1000, -100, -99, -10, 1, 10, 11, 100 };
   
9.                 int a[2*n] = {-19, -5, -1, 3, 7, 11, 13, 17};
   
10.                 int sum1 = 0, sum2 = 0;
    
11.                 int a1[n], a2[n];
    
12.                 int count1 = 0, count2 = 0;
    
13.                 //按绝对值降序排序
    
14.                 std::sort(a, a + 2 * n, compare);
    
15. 
    
16.                 for(int i = 0; i < 2 * n; ++i) {
    
17.                         if(count1 == n) { //如果数组1满了
    
18.                                 sum2 += a[i];
    
19.                                 a2[count2++] = a[i];
    
20.                         } else if(count2 == n) {//如果数组2满了
    
21.                                 sum1 += a[i];
    
22.                                 a1[count1++] = a[i];
    
23.                         } else if(sum1 == sum2) {//特殊情况处理
    
24.                                 if(count1 < count2) {
    
25.                                         sum1 += a[i];
    
26.                                         a1[count1++] = a[i];
    
27.                                 } else {
    
28.                                         sum2 += a[i];
    
29.                                         a2[count2++] = a[i];
    
30.                                 }
    
31.                         } else if(sum1 < sum2 && a[i] > 0 || sum1 > sum2 && a[i] < 0){
    
32.                                 sum1 += a[i];
    
33.                                 a1[count1++] = a[i];
    
34.                         } else {
    
35.                                 sum2 += a[i];
    
36.                                 a2[count2++] = a[i];
    
37.                         }
    
38.                 }
    
39. 
    
40.                 std::cout << "a1:\n";
    
41.                 for(int i : a1) {
    
42.                         std::cout << i << ' ';
    
43.                 }
    
44.                 std::cout << "\na2:\n";
    
45.                 for(int i : a2) {
    
46.                         std::cout << i << ' ';
    
47.                 }
    
48.                 std::cout << '\n';
    
49.         }
    

复制代码

lost_templar

1. void mono_swap( int* a, int* b, const unsigned long n )
   
2. {
   
3.     int sum_a = std::accumulate( a, a+n, 0 );
   
4.     int sum_b = std::accumulate( b, b+n, 0 );
   
5.     const int sum = sum_a + sum_b;
   
6.     const int min_diff = sum & 1 ? 1 : 0;
   
7. 
   
8.     int diff = sum_a - sum_b;
   
9. 
   
10.     if ( std::abs(diff) == min_diff ) return;
    
11. 
    
12.     std::sort( a, a+n );
    
13.     std::sort( b, b+n );
    
14. 
    
15.     for ( unsigned long i = 0; i != n; ++i )
    
16.         for ( unsigned j = 0; j != n; ++j )
    
17.         {
    
18.             const int new_diff = diff - a[i] - a[i] + b[j] + b[j];
    
19.             if ( std::abs(new_diff) < std::abs(diff) )
    
20.             {
    
21.                 std::swap( a[i], b[i] );
    
22.                 return mono_swap( a, b, n );
    
23.             }
    
24.         }
    
25. }
    

复制代码

yezj2004

谢谢楼主！！！！

woyaoying

先算出两个abs(sum(a)-sum(b))之间的差值，然后循环遍历A和B，笛卡尔方式遍历，然后尝试交换A和B之间的值，如果交换后发现差值更小了，则交换，如果更大则不交换，直到所有的都无法交换为止，下面的代码效率不高，但这个问题这样解释最让人理解。

1. 
   
2.         public void swapToMinusDiff(int[] a,int[] b){
   
3.                 int sumA = sum(a);
   
4.                 int sumB = sum(b);
   
5.                
   
6.                 if(sumA == sumB)
   
7.                         return;
   
8.                
   
9.                 int len = a.length;
   
10.                
    
11.                 int diff = Math.abs(sum(a) - sum(b));
    
12.                 int count = 0;
    
13. 
    
14.                 do {
    
15.                         count = 0;
    
16.                         for(int i = 0; i < len; i++) {
    
17.                                 for(int j = 0; j < len; j++) {
    
18.                                         swap(a, b, i, j);
    
19.                                         int temp = Math.abs(sum(a) - sum(b));
    
20.                                         if (temp > diff) {
    
21.                                                 swap(a, b, j, i); // 差更大了，所以不交换了。
    
22.                                                 count++;
    
23.                                         }        else {
    
24.                                                 diff = temp;
    
25.                                         }
    
26.                                 }
    
27.                         }
    
28.                 } while (count < (len*len));
    
29.        
    
30.                 System.out.println("the min diff is " + diff);
    
31.         }
    

复制代码

被你发现了

回复 389# woyaoying
通过单个元素交换，只能得到更小，不能保证得到最小。