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

su_787910081

八年前的帖子了。

看了十几页真心很累，不过大概看到的都是将两个数组合并之后再分，不知道对与不对。
不过我是想过很多种将两个数组合并后再填充的情况，多种情况都被我否定了，之后想到了一种不全并的算法，暂时还没想到有什么情况否定的。思路如下：

1、将A、B数组分别排序；
2、申请一个数组C 与A、B数组一样，该数组用于存放A、B数组对应下标处元素之差(即：C = A - B);
3、申请一个数组D，按C数组中最大值到最小值的顺序存放C数组中的下标(即：C数组中元素从大到小排序后的下标的记录，为的是后面从最大差值开始顺序交换作铺垫)；
4、算法从此处开始：
1)、记录A、B数组谁的元素之和谁更大；// 目的是，假设刚开始A 数组之和 大于 B 数组 之和，而第2)步中的循环退出条件就是要B数组之和大于A数组之和，反过来。
2)、取数组D中的元素作为数组C中元素的下标做循环(即：按A、B元素对应下标处的最大差值开始)，每次循环交换该对应下标，此时数组A、B元素之和改变，然后重新计算A、B数组的元素和之差，若该差值反向(即：之前为A数组元素和大于B数组元素和，而现在是B数组元素和大于A数组元素和)，则循环结束。此时A、B数组中的元素和之差应该是最小的了。

非常想把步骤写清楚，毕竟是一个算法，挺复杂的，但是我已经尽力，实在没有好的文采。
想了好久，不断重复查看题目，想出来的这个。其实我也不确定它的正确性。不过挺好玩的，呵呵！
{:3_200:}

dididimeme01

想了一下，觉得应该可以这样做：
方法一：
     先排序，然后采用篮子取果子的方式，即在所有排序好的篮子中找找果子，分别放在原先的数组为N的A和B中，每次放都检查之间的和差，从而确定当前元素是放到A中还是放到B中。最终将排序好的队列数据都放到A和B中了，所得到的就是最小和差；
方法二：
    如果懒一点，我不进行排序是否可以呢？我想了一下，如果以AB两个集合，做一个两重循环，即A中第一个元素与B中元素逐个交换，每次交换看和差是否有变化，如果变小了，则交换实现，从头再来，如果都没有变化则证明A这个元素是它中元素，接着第二个，直到最后一个完成，你会发现A与B中元素就是这样的最好和差。另外要提到的是，第一个元素交换后，还是需要从它进行比较的，即从B交换来的数据，是否就是A中的呢不一定，只有在与B中的都比较后，和差最小才是A中的。
   以上就是我的想法，不知道对不。

dididimeme01

又想了一下，第一种方法有缺陷，即AB都是N的静态数组，如果出现取过程中其中一个数据被填写满了，则后面的数据只能都放到另一个数组中，这样可能出现的结果不是最小和差了。

tonyauyeung

a+b 排序后为c
然后轮流取数 分别各取1个为1次
--------------------------------------------------
先比较a b 元素之和
小的先取  相等随意

小的 先取剩余数中最大的
然后再看刚才未取数的集合之和  如果 大于等于先取数的集合则取剩余中最小数  如果小于则取最大数
----------------
重复上述过程

dididimeme01

其实，主要发现这样的例子不适用于排序法
A数组为 0、1、2、3、4 B数组为 5、6、7、8、20000，如果排序后取的话，应该是A 0、2、4、6、8  B数组1、3、5、 7、20000，但是其结果不是正确的，因为正常的值差，A为4、5、6、7、8  B为0、1、2、3、4、20000会更小的。所以，感觉我的第二种方法是可行的。

dididimeme01

还有一种办法就是排倒序，之后从后面取数放，每次计算和差那边小就放那边，结果也是对的，即B 20000、4、3、2、1 A为8、7、6、5、4.

天涯笑

算法有问题，删掉准备重写！

vbs100

写了个错误代码，删掉

vbs100

感觉这个应该是对的了，大致思路是这样的:
1. 用一个N*N数组C，保存A B数组任的意两个数字的数字差和这两个数在A B数组中对应的下标，并按数字差的大小排序
2. 根据当前A B两个数组的和差，在C中找到一个数字差区间[2*Xi,2*Xj]，使得和差正好落在这个区间上，计算两个端点代表的交换在交换后的和差，在这三个和差中取绝对值最小的
3. 交换选中的A B数组中两个选定的数，更新数组和差、更新数组C，重复过程2直到结束


终止条件：
1. 当前和差为0
2. 当前和差比两个新计算出来的和差都小

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <time.h>
   
5. 
   
6. #define N 10
   
7. 
   
8. struct delta
   
9. {
   
10.         int i;
    
11.         int j;
    
12.         int d;
    
13. };
    
14. 
    
15. int a[N];
    
16. int b[N];
    
17. struct delta c[N][N];
    
18. 
    
19. int compar(const void *a1, const void *a2)
    
20. {
    
21.         return ((struct delta*)a1)->d - ((struct delta*)a2)->d;
    
22. }
    
23. 
    
24. void swap(int *a, int *b)
    
25. {
    
26.         int tmp;
    
27.         tmp = *a;
    
28.         *a = *b;
    
29.         *b = tmp;
    
30. }
    
31. 
    
32. void update(int i, int j)
    
33. {
    
34.         struct delta *p;
    
35.         for(p = &c[0][0]; p <= &c[N-1][N-1]; p++)
    
36.         {
    
37.                 if(p->i == i)
    
38.                         p->d = a[i]-b[p->j];
    
39.                 if(p->j == j)
    
40.                         p->d = a[p->i]-b[j];
    
41.         }
    
42.         qsort(&c, N * N, sizeof(struct delta), &compar);
    
43. }
    
44. 
    
45. int sum(int array[])
    
46. {
    
47.         int i, sum=0;
    
48.         for(i = 0; i < N; i++)
    
49.                 sum += array[i];
    
50.         return sum;
    
51. }
    
52. 
    
53. void print(int array[])
    
54. {
    
55.         int i;
    
56.         for(i = 0; i < N; i++)
    
57.                 printf("%d ", array[i]);
    
58.         printf("\n");
    
59. }
    
60. 
    
61. void findsection(int dsum, struct delta **d1, struct delta **d2)
    
62. {
    
63.         struct delta *p, *q;
    
64.         if(dsum <= c[0][0].d * 2)
    
65.         {
    
66.                 *d1 = NULL;
    
67.                 *d2 = &c[0][0];
    
68.                 return;
    
69.         }
    
70.         if(dsum >= c[N-1][N-1].d * 2)
    
71.         {
    
72.                 *d1 = &c[N-1][N-1];
    
73.                 *d2 = NULL;
    
74.                 return;
    
75.         }
    
76.         for(p = &c[0][0], q = p + 1; q <= &c[N-1][N-1]; p++, q++)
    
77.         {
    
78.                 if(dsum >= p->d * 2 && dsum <= q->d * 2)
    
79.                 {
    
80.                         *d1 = p;
    
81.                         *d2 = q;
    
82.                         break;
    
83.                 }
    
84.         }
    
85. }
    
86. 
    
87. int main()
    
88. {
    
89.         int i,j,k;
    
90.         int sum_a,sum_b,sum_ab;
    
91. 
    
92.         srand(time(NULL));
    
93.         for(i = 0; i < N; i++)
    
94.         {
    
95.                 a[i] = rand()%100;
    
96.                 b[i] = rand()%100;
    
97.         }
    
98. 
    
99.         for(i = 0; i < N; i++)
    
100.         for(j = 0; j < N; j++)
     
101.         {
     
102.                 c[i][j].i = i;
     
103.                 c[i][j].j = j;
     
104.                 c[i][j].d = a[i]-b[j];
     
105.         }
     
106.         qsort(&c, N * N, sizeof(struct delta), &compar);
     
107. 
     
108.         while(1)
     
109.         {
     
110.                 struct delta *p1 ,*p2;
     
111.                 sum_a = sum(a);
     
112.                 sum_b = sum(b);
     
113.                 sum_ab = sum_a - sum_b;
     
114.                 print(a);
     
115.                 print(b);
     
116.                 printf("sum(a)=%d sum(b)=%d sum(a)-sum(b)=%d\n", sum_a, sum_b, sum_ab);
     
117. 
     
118.                 if(sum_ab == 0)
     
119.                         break;
     
120. 
     
121.                 findsection(sum_ab, &p1, &p2);
     
122. 
     
123.                 if(p1 == NULL)
     
124.                 {
     
125.                         i = p2->i;
     
126.                         j = p2->j;
     
127.                         swap(&a[i],  &b[j]);
     
128.                         update(i, j);
     
129.                 }
     
130.                 else if(p2 == NULL)
     
131.                 {
     
132.                         i = p1->i;
     
133.                         j = p1->j;
     
134.                         swap(&a[i],  &b[j]);
     
135.                         update(i, j);
     
136.                 }
     
137.                 else
     
138.                 {
     
139.                         if(abs(sum_ab - p1->d*2) <= abs(sum_ab - p2->d*2))
     
140.                         {
     
141.                                 if(abs(sum_ab)<=abs(sum_ab - p1->d*2))
     
142.                                         break;
     
143.                                 swap(&a[p1->i],  &b[p1->j]);
     
144.                                 update(p1->i, p1->j);
     
145.                         }
     
146.                         else
     
147.                         {
     
148.                                 if(abs(sum_ab)<=abs(sum_ab - p2->d*2))
     
149.                                         break;
     
150.                                 swap(&a[p2->i],  &b[p2->j]);
     
151.                                 update(p2->i, p2->j);
     
152.                         }
     
153.                 }
     
154. 
     
155.         }
     
156.         return 0;
     
157. }
     

复制代码

下面是n=10，随机生成a b数组的计算结果，基本上都是5次之内就可以完成交换，收敛的速度还是非常快的

vbs100@ubuntu:~$ ./a.out
41 83 53 2 46 31 11 91 44 16
69 40 84 17 99 58 49 34 93 83
sum(a)=418 sum(b)=626 sum(a)-sum(b)=-208
41 83 53 99 46 31 11 91 44 16
69 40 84 17 2 58 49 34 93 83
sum(a)=515 sum(b)=529 sum(a)-sum(b)=-14
49 83 53 99 46 31 11 91 44 16
69 40 84 17 2 58 41 34 93 83
sum(a)=523 sum(b)=521 sum(a)-sum(b)=2
vbs100@ubuntu:~$
vbs100@ubuntu:~$ ./a.out
12 32 15 60 25 41 96 30 0 57
8 98 72 76 11 85 48 33 78 91
sum(a)=368 sum(b)=600 sum(a)-sum(b)=-232
12 32 15 60 25 41 96 30 98 57
8 0 72 76 11 85 48 33 78 91
sum(a)=466 sum(b)=502 sum(a)-sum(b)=-36
12 32 33 60 25 41 96 30 98 57
8 0 72 76 11 85 48 15 78 91
sum(a)=484 sum(b)=484 sum(a)-sum(b)=0
vbs100@ubuntu:~$
vbs100@ubuntu:~$ ./a.out
14 64 88 21 71 42 70 50 18 38
83 38 29 52 72 30 5 83 63 23
sum(a)=476 sum(b)=478 sum(a)-sum(b)=-2
14 64 88 21 72 42 70 50 18 38
83 38 29 52 71 30 5 83 63 23
sum(a)=477 sum(b)=477 sum(a)-sum(b)=0
vbs100@ubuntu:~$
vbs100@ubuntu:~$ ./a.out
68 99 28 87 66 45 8 18 55 78
62 67 46 90 74 44 9 15 77 51
sum(a)=552 sum(b)=535 sum(a)-sum(b)=17
68 90 28 87 66 45 8 18 55 78
62 67 46 99 74 44 9 15 77 51
sum(a)=543 sum(b)=544 sum(a)-sum(b)=-1

vbs100

感觉这个题就是个坑，题目里面根本就没有提到绝对值，只说了数组a元素的和与数组b元素的和之间的差最小，意思就是说sum(a)-sum(b)最小，所以这个题最简单的办法就是把最小的n个数都换到数组a中，这样差就最小了