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

bjtuwg

a = a1 a2 a3 ... an
b = b1 b2 b3 ... bn

合并a b到数组c并排序   c = c1 c2 c3 ... c2n

1.将c2n 赋给 a
2.将c2n-1 赋值给 b
3.for(int i = 2n-2; i >= 0; i--)           //写法不太准确，意思循环剩下的c数组
{
    if(b数组之和+ci < a数组之和)          //可能有些问题，if(b数组之和+ci < a数组之和)，此时ci不好判断是放在a里还是b里  还是说循环放一次放a 下一次放b
         将ci赋值给b
         将ci 从数组c中删除(标记下次不再取就行)
}

晓得飞天千秋雪

以前给过一种方法：http://kan.weibo.com/con/3562687971904001?_from=title

现在再给一种方法：http://kan.weibo.com/con/3589946288520547?_from=title

mcyeah

这个不是典型的插入排序吗？  但是我不知道怎么写代码了   得复习去啦

zxjcarrot

先把两个数组合并到一起从大到小排序,然后从头开始取数,如果当前数组A的和大于数组B的和,让B取，否则A取,如果A数组的数量到了n个就都让B取,B反之亦然.

aaaa9813

#include "stdio.h"
#include "stdlib.h"

int a[] = {6,0,8};
int b[] = {2,1,9};


int getsum()
{
       int sum = 0;
        int sum1 = 0;
        for(int i = 0; i < 3; i++)
        {
                sum += a[i];
                sum1 += b[i];
        }
        return abs(sum - sum1);
}

int main()
{
        int tt = getsum();
        for(int i = 0; i < 3; i++)
        {
                for(int j = 0; j < 3; j++)
                {
                        int t = a[i];
                        a[i] = b[j];
                        b[j] = t;
                        if(getsum() < tt)
                        {
                                tt = getsum();
                        }
                        else
                        {
                                t = a[i];
                                a[i] = b[j];
                                b[j] = t;
                        }

                }
        }

        for(int i = 0; i < 3; i++)
        {
                printf("%d, %d\n", a[i], b[i]);
        }
        return 0;
}

potterhe

xmyth 发表于 2006-11-14 17:04
当前数组a和数组b的和之差为
A = sum(a) - sum(b)

1. /**
   
2. * http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=855126&page=8#pid6022430
   
3. */
   
4. #include <stdio.h>
   
5. #include <stdlib.h>
   
6. #include <math.h>
   
7. #include <time.h>
   
8. 
   
9. int
   
10. sum_array(int *a, int n)
    
11. {
    
12.         int i, sum = 0;
    
13.         for(i = 0; i < n; i++)
    
14.                 sum += a[i];
    
15.         return sum;
    
16. }
    
17. 
    
18. void
    
19. do_swap(int *a, int *b, int n)
    
20. {
    
21.         int A, i, j, x, d, m, si, sj, *ap, *bp;
    
22. 
    
23. do_start:
    
24.         i = sum_array(a, n);
    
25.         j = sum_array(b, n);
    
26.         A = i - j;
    
27.         ap = a;
    
28.         bp = b;
    
29.         if(A < 0) {
    
30.                 ap = b;
    
31.                 bp = a;
    
32.                 A = j - i;
    
33.         }
    
34.        
    
35.         m = A;
    
36.         si = sj = -1;
    
37.         for(i = 0; i < n; i++){
    
38.                 for(j = 0; j < n; j++) {
    
39.                         x = ap[i] - bp[j];
    
40.                         if(x > 0 && x < A) {
    
41.                                 d = abs((x * 2) - A);
    
42.                                 if(d < m) {
    
43.                                         m = d;
    
44.                                         si = i;
    
45.                                         sj = j;
    
46.                                 }
    
47.                         }
    
48. 
    
49.                 }
    
50.         }
    
51. 
    
52.         if(si != -1) {
    
53.                 i = ap[si];
    
54.                 ap[si] = bp[sj];
    
55.                 bp[sj] = i;
    
56.                 goto do_start;
    
57.         }
    
58. }
    
59. 
    
60. void
    
61. dump_array(int *a, int n)
    
62. {
    
63.         int i;
    
64.         printf("\n");
    
65.         for(i = 0; i < n; i++) {
    
66.                 printf(" %d ", a[i]);
    
67.         }
    
68. }
    
69. 
    
70. void
    
71. mk_rand_int_array(int *a, int n)
    
72. {
    
73.         int i, r;
    
74.         for(i = 0; i < n; i++) {
    
75.                 r = rand(100);
    
76.                 a[i] = r % 101; //* ( r % 2 ? 1 : -1);
    
77.         }
    
78. }
    
79. 
    
80. int
    
81. main()
    
82. {
    
83.         int n = 3;
    
84.         int a[] = {999, 1, 0};
    
85.         int b[] = {1, 0, 2};
    
86. 
    
87.         do_swap(a, b, n);
    
88.         dump_array(a, n);
    
89.         dump_array(b, n);
    
90. 
    
91.         int n2 = 4;
    
92.         int a2[] = {1, 2, 3, 4};
    
93.         int b2[] = {5, 6, 7, 8};
    
94. 
    
95.         do_swap(a2, b2, n2);
    
96.         dump_array(a2, n2);
    
97.         dump_array(b2, n2);
    
98. 
    
99.         int n3 = 5;
    
100.         int a3[n3], b3[n3];
     
101.         mk_rand_int_array(a3, n3);
     
102.         mk_rand_int_array(b3, n3);
     
103. 
     
104.         do_swap(a3, b3, n3);
     
105.         dump_array(a3, n3);
     
106.         dump_array(b3, n3);
     
107. 
     
108.         exit(0);
     
109. }
     

复制代码

fisherFIAF

这个题目，如果只是达到结果，那可以创造一个 2N 的数组C， 把数组A B 的元素都放到C里面，
对数组C排序， 再把C的前N个放到A， 后N个放到B。
这样比较简单吧，比起A和B之间互换元素要方便，就是多占用了内存。

jason_kok

放到一个临时数组里排序后，两头取，分别存在a,b里


如果存在这样一个数，它比所有的数加起来都要大的多，这个就不能实现了吧。

Xkoma

根据21楼同学的思路写的代码，我认为思路是对的

1. #include <stdio.h>
   
2. #include <malloc.h>
   
3. 
   
4. void swap(int *a,int *b)
   
5. {
   
6.   int temp = 0;
   
7.       temp = *a;
   
8.       *a = *b;
   
9.       *b = temp;
   
10. }
    
11. 
    
12. void sort(int *a,int *b,int *c,int n)
    
13. {
    
14.   int i = 0,j = 0,temp = 0;
    
15. 
    
16.   for( i = 0; i < 2*n; i++)
    
17.   {
    
18.     if(i < n) {
    
19.       c[i] = a[i];
    
20.     }else{
    
21.       c[i] = b[j];
    
22.       j++;
    
23.     }
    
24.   }
    
25. 
    
26.   for(j = 0; j < 2*n-1; j++)
    
27.     for(i = 0; i < 2*n -j-1 ; i++)
    
28.          if(c[i] < c[i+1]) {swap(&c[i],&c[i+1]);}
    
29. }
    
30. 
    
31. void array_lleast(int *a,int *b,int n)
    
32. {
    
33.   int i = 0, asum = 0,bsum = 0,acount = 0,bcount = 0;
    
34.   int *c =  (int *)malloc(2*n*sizeof(int));
    
35. 
    
36.   sort(a,b,c,n);
    
37.   while((acount < n) && (bcount < n))
    
38.   {
    
39.     if(asum <= bsum) {
    
40.       a[acount] = c[acount+bcount];
    
41.       asum += a[acount];
    
42.       acount++;
    
43.     }else{
    
44.       b[bcount] = c[acount+bcount];
    
45.       bsum += b[bcount];
    
46.       bcount++;
    
47.     }
    
48.   }
    
49. 
    
50.   if(acount >= n){
    
51.     for(i = bcount; i < n; i++)
    
52.            b[i] = c[n+i];
    
53.   }else{
    
54.         for(i = acount; i < n; i++)
    
55.            a[i] = c[n+i];
    
56.   }
    
57. }
    
58. 
    
59. 
    
60. int main()
    
61. {
    
62.   int a[] = { 26, 25, 18, 36, 18, 48, 19, 51};
    
63.   int b[] = {12,12,13,11,85,14,94,13};
    
64.   int i = 0,sum = 0;
    
65. 
    
66.   array_lleast(a,b,8);
    
67.   
    
68.   for(i = 0; i < 8; i++)
    
69.     sum += a[i]-b[i];
    
70. 
    
71.   if(sum < 0) sum = -sum;
    
72.   printf("%d ",sum);
    
73. return 0;
    

复制代码

ubanwin

有两个数组a,b，大小都为n,数组元素的值任意，无序；
要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小。

既然说明了是可以交换a,b中的元素，而且a,b元素都是n，那么只要再申明一个临时数组c，其中存放a,b中的元素，对其进行排序，然后将c中相邻元素相减（diff+=c[i+1]-c[i];i+=2;//这里是从小到大排序），最后得到的diff就是最小差之和了。

举例说明  如果a中含1，3，5  b中含2，4，6   在这样的情况下貌似2楼的方法可行，但是如果换成a:1,2,3   b:4,5,6   这样就不行，而把a,b中的元素放到同一个数组里面就不会出现这种情况。

楼上所提让我类似的想到快速排序法的数轴。。。