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

独一无wy

我的想法是：先对两数组进行整体排序，然后从大到小的分配到两数组中，比如排序后为[a,b,c,d,e,f] 分配a,b数组为 [a,d,e][b,c,f];
不知是否可行？

device_memory

                              

palm008

7楼威武，学习

lvzhiqiang1990

1.计算当前两坨数据a-b=m（假设a>b）
2.计算两坨数据中差值最小的两个数a（i）、b（j），假设其差为m1    （a（i）>b(j)）
3.如果2*m1>m,则此时达到差值最小
4.若3不成立，交换a(i)、b(j)，更新m=m-2*m1，更新m1，此时只用计算调换过来的数据与原来数据的差值最小值
重复3、4即可

基本思想是如果二者差已经最小了，则较大的一堆里面与较小的一堆里面的数的差值的2倍必然超过总和的差，否则的话就可以通过调整二者从而减小总和的差。

hh_gavin

我的思路是：
a0、a1、b0和b1先进行比较交换，然后a0和a1之和、b0和b1之和、a2和b2进行比较交换，以此类推。
全部元素比较完之后，再从最后元素用相同方法倒过来比较交换一次。

下面是我编写的代码：

1. #include <stdio.h>
   
2. 
   
3. void swap(unsigned int *pa1, unsigned int *pa2, unsigned int *pb1, unsigned int *pb2)
   
4. {
   
5.         unsigned int sort[4];
   
6.         unsigned int tmp;
   
7.         int i,j;
   
8.         sort[0] = *pa1;
   
9.         sort[1] = *pa2;
   
10.         sort[2] = *pb1;
    
11.         sort[3] = *pb2;
    
12.        
    
13.         for (i = 4; i > 0; i--)
    
14.         {
    
15.                 for (j = 0; j < i-1; j++)
    
16.                 {
    
17.                         if (sort[j] > sort[j + 1])
    
18.                         {
    
19.                                 tmp = sort[j];
    
20.                                 sort[j] = sort[j + 1];
    
21.                                 sort[j + 1] = tmp;
    
22.                         }
    
23.                 }
    
24.         }
    
25.        
    
26.         *pa1 = sort[0];
    
27.         *pa2 = sort[3];
    
28.         *pb1 = sort[1];
    
29.         *pb2 = sort[2];
    
30.        
    
31.         return;
    
32. }
    
33. 
    
34. void my_printf(int *p, int num)
    
35. {
    
36.         int i;
    
37.         for (i = 0; i<num; i++)
    
38.         {
    
39.                 printf("%d  ", p[i]);
    
40.         }
    
41.         printf("\n");
    
42.         return;
    
43. }
    
44. 
    
45. int main()
    
46. {
    
47.         unsigned int a[10];
    
48.         unsigned int b[10];
    
49.         unsigned int sum_a = 0;
    
50.         unsigned int sum_b = 0;
    
51.         unsigned int tmp;
    
52.         int i;
    
53.        
    
54.         printf("###########aaaaaaa##########\n");
    
55.         my_printf(a, 10);
    
56.         printf("###########bbbbbbb##########\n");
    
57.         my_printf(b, 10);
    
58.         swap(&a[0], &a[1], &b[0], &b[1]);
    
59.         sum_a = a[0] + a[1];
    
60.         sum_b = b[0] + b[1];
    
61.        
    
62.         for (i = 2; i < 10; i++)
    
63.         {
    
64.                 if (sum_a > sum_b)
    
65.                 {
    
66.                         if (a[i] > b[i])
    
67.                         {
    
68.                                 tmp = a[i];
    
69.                                 a[i] = b[i];
    
70.                                 b[i] = tmp;
    
71.                         }
    
72.                        
    
73.                 }
    
74.                 else
    
75.                 {
    
76.                         if (a[i] < b[i])
    
77.                         {
    
78.                                 tmp = a[i];
    
79.                                 a[i] = b[i];
    
80.                                 b[i] = tmp;
    
81.                         }
    
82.                 }
    
83.                 sum_a += a[i];
    
84.                 sum_b += b[i];
    
85.         }
    
86.        
    
87.         printf("###########aaaaaaa##########\n");
    
88.         my_printf(a, 10);
    
89.         printf("###########bbbbbbb##########\n");
    
90.         my_printf(b, 10);
    
91.        
    
92.         swap(&a[9], &a[8], &b[9], &b[8]);
    
93.         sum_a = a[8] + a[9];
    
94.         sum_b = b[8] + b[9];
    
95.         for (i = 7; i >= 0; i--)
    
96.         {
    
97.                 if (sum_a > sum_b)
    
98.                 {
    
99.                         if (a[i] > b[i])
    
100.                         {
     
101.                                 tmp = a[i];
     
102.                                 a[i] = b[i];
     
103.                                 b[i] = tmp;
     
104.                         }
     
105.                        
     
106.                 }
     
107.                 else
     
108.                 {
     
109.                         if (a[i] < b[i])
     
110.                         {
     
111.                                 tmp = a[i];
     
112.                                 a[i] = b[i];
     
113.                                 b[i] = tmp;
     
114.                         }
     
115.                 }
     
116.                 sum_a += a[i];
     
117.                 sum_b += b[i];
     
118.         }
     
119.         printf("###########aaaaaaa##########\n");
     
120.         my_printf(a, 10);
     
121.         printf("###########bbbbbbb##########\n");
     
122.         my_printf(b, 10);
     
123.        
     
124.         return 0;
     
125. }

复制代码

rag

c代码好多年不写了，写不出来了。

我的思路是这样的

分别求出数组a、b的和，以及a、b和的差，差值取绝对值，以下皆同；
遍历数组单元的次数；
遍历数组，找出，a、b各自的最大值，最小值；
数组a的和大于b的和，分析计算a的最大值与b的最小值的差，否则计算b的最大值与a的最小值差。比较，如果大，找下一个次最大值，计算比较，小，且交换后的和差绝对值小于但前差，交换，修正a、b各自的和，否则，结束。将当前置换值替换值a、b各自的最大值、最小值，重复此步骤，直到满足条件：a的最大值=最小值或者b的最大值=最小值，或者遍历数组的次数完毕。

nick97

这题有那么复杂么  
元素个数n 求出组合序列然后再依次求和 - 总和/2 再求绝对值 取最小的一对

1234
5678
总和为36 除以2 18

1234     |1+2+3+4 - 18| = 8
1235     |1+2+3+5 - 18| = 7
。。。
只是要手写的话太麻烦。。 要累死人了

liangmaogu

     1 #include <stdio.h>
      2 #include <stdlib.h>
      3
      4 void swap(int *a, int *b) {
      5     int tmp = *a;
      6     *a = *b;
      7     *b = tmp;
      8 }
      9
     10 int sum(int arr[], int len) {
     11     int tmpSum = 0;
     12     int i = 0;
     13     for (; i < len; i++) {
     14         tmpSum += arr[i];
     15     }
     16     return tmpSum;
     17 }
     18
     19 int comp(const void *p, const void *q) {
     20     return (*(int*)p - *(int*)q);
     21 }
     22
     23 int main(int argc, char *argv[]) {
     24     int arr[] = {10, 45, 69, 78, 36};
     25     int brr[] = {25, 85, 71, 63, 42};
     26
     27     int asum = 0;
     28     int bsum = 0;
     29     int tmpSum = 0;
     30     int len = 5;
     31     int i = 0;
     32
     33     qsort(arr, len, sizeof(int), comp);
     34     qsort(brr, len, sizeof(int), comp);
     35
     36     asum = sum(arr, len);
     37     bsum = sum(brr, len);
     38     tmpSum = abs(asum - bsum);
     39     printf("asum = %d, bsum = %d, tmpSum = %d\n", asum, bsum, tmpSum);
     40     
     41     for (i = len -1; i >= 0; i--) {
     42         swap(&arr[i], &brr[i]);
     43         asum = sum(arr, len);
     44         bsum = sum(brr, len);
     45         
     46         if (tmpSum > abs(asum - bsum)) {
     47             tmpSum = abs(asum - bsum);
     48         } else {
     49             swap(&arr[i], &brr[i]);
     50         }
     51         printf("asum = %d, bsum = %d, tmpSum = %d\n", asum, bsum, tmpSum);
     52     }
     53     
     54     return 0;
     56 }

zeorro

哦知道了，最短路径问题，或者背包问题