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

mmx_craft

以下思路如何， 先把a,b合成一个2n的数组C, 然后按照如下规则选取。
  1. a[0] = c [2n-1], b[0] = c[2n-2]
  2. 按照suma>sumb, 取剩下的最大的给b，最小的给a； 反之最大的给a，最小的给b。

程序如下：

#include <stdio.h>
#include <stdlib.h>

static int
intcompare(const void *p1, const void *p2)
{
    int i = *((int *)p1);
    int j = *((int *)p2);

    if (i > j)
        return (1);
    if (i < j)
        return (-1);
    return (0);
}

int change(int *a, int *b, int size)
{
    int *c = (int*) malloc(2*size);
    int pos_a,pos_b,pos_c,pos_cend;
    int sum_a,sum_b;
    int i;

    memcpy(c, a, sizeof(int)*size);
    memcpy(c+size, b, sizeof(int)*size);
   
    qsort((void *)c, 2*size, sizeof (int), intcompare);

    pos_a=pos_b=pos_c=0;
    pos_cend = 2*size-1;
    a[pos_a++] = c[pos_cend--];
    b[pos_b++] = c[pos_cend--];
    sum_a = a[0];
    sum_b = b[0];
   
    while (pos_cend > pos_c ) {
        if (sum_a > sum_b) {
            a[pos_a++] = c[pos_c++];
            b[pos_b++] = c[pos_cend--];
            sum_a += a[pos_a-1];
            sum_b += b[pos_b-1];
        } else {
            a[pos_a++] = c[pos_cend--];
            b[pos_b++] = c[pos_c++];
            sum_a += a[pos_a-1];
            sum_b += b[pos_b-1];
        }
    }
}

int main (int argc, char **argv)
{
    int a[6]= {1, 2, 3,4,5,6};
    int b[6]= {7, 8, 9,10,11,12};
    int i;
   
    change(a,b,6);


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

xmyth

当前数组a和数组b的和之差为
A = sum(a) - sum(b)

a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])
       = sum(a) - sum(b) - 2 (a[i] - b[j])
       = A - 2 (a[i] - b[j])
设x = a[i] - b[j]

|A| - |A'| = |A| - |A-2x|

假设A > 0,

当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好,

如果找不到在(0,A)之间的x，则当前的a和b就是答案。

所以算法大概如下：

在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。

[[i] 本帖最后由 xmyth 于 2006-11-14 20:45 编辑 [/i]]

flw2

xmyth 快四年一贴啊.

你说的我看懂了

cuicp

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

a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
       = sum(a) - sum(b) - 2 (a - b[j]) ...

想法很好呀，又有数学证明，但是什么时候会
找不到（0,A）之间的x呢？
比如：
1，2，3，4，5，12
最佳方案好像是：
4，5，3
1，2，12

那么0<（3－2）<(15-12)

好像不行呀？
是不是要改进一下结束的条件？
我考虑的对不对？
高手看看！
谢谢！！

xmyth

这个结束条件应该是没有问题的

在你说的这个例子里，已经满足了我所提出的结束条件

前面我假设了A>0 (如果A不大于0，对换一下就好了)

所以这里a = {1,2,12}; b = {4,5,3};

x=a[i]-b[j]

所有的x应该都不能满足（0, 3)的条件了，所以满足结束条件了。

exir

真的只有八分钟吗？字都打不完啊。

flw2

原帖由 xmyth 于 2006-11-14 20:44 发表
这个结束条件应该是没有问题的

在你说的这个例子里，已经满足了我所提出的结束条件

前面我假设了A>0 (如果A不大于0，对换一下就好了)

所以这里a = {1,2,12}; b = {4,5,3};

x=a-b[j]

所有的x ...

我一眼就感觉你那公式很可能是对的
这种类似的题很多的
比如100个红包，7个人分，怎么分才最均匀，是不是更头疼？

flw2

greensky_34

用二重循环把a中的每个元素和b中的每个元素逐个“尝试交换”，
如果是差值变小就维持交换，否则就交换回去，也就是不交换，
每有一次交换，“尝试交换”的二重循环就重新从头开始，
直到没有任何交换使差值变小为止。
这种方法不是很简洁，但的确是可行的。
前边贴出代码的算法，有过一次交换后，循环没有从头开始，所以是错误的。例如a[1]和b[j]交换后，b中的元素改变了，不能再保证a[0]和b[ i ]交换不会使差值变小，这时循环必须从头开始。

1. 
   
2. #include <stdio.h>
   
3. #include <math.h>
   
4. 
   
5. #define N 10
   
6. 
   
7. void ary_init(int a[], int b[]){ //初始化数组
   
8.     int i;
   
9.     for (i=0; i<N; i++){
   
10.         a[i] = rand()%10000;
    
11.     }
    
12.     for (i=0; i<N; i++){
    
13.         b[i] = rand()%100;
    
14.     }
    
15.     return;
    
16. }
    
17. long sum(int a[]){ //数组求和
    
18.     int i;
    
19.     int s;
    
20.     for (s=0,i=0; i<N; i++){
    
21.         s += a[i];
    
22.     }
    
23.     return s;
    
24. }
    
25. 
    
26. void change(int *a, int *b){ //数组元素交换
    
27.     int tmp;
    
28.     tmp = *a;
    
29.     *a = *b;
    
30.     *b = tmp;
    
31.     return;
    
32. }
    
33. 
    
34. void prt_ary(int a[], int b[]){ //列印两数组元素及各自元素和
    
35.     int i;
    
36.     for(i=0; i<N; i++){
    
37.         printf("%5d   ", a[i]);
    
38.     }
    
39.     printf("\n");
    
40.     for(i=0; i<N; i++){
    
41.         printf("%5d   ", b[i]);
    
42.     }
    
43.     printf("\n");
    
44.     printf("%d\n", sum(a));
    
45.     printf("%d\n", sum(b));
    
46. }
    
47. int slove(int a[], int b[]){
    
48.     int i;
    
49.     int j;
    
50.     int is_swap = 0;//是否修交换过数据标志
    
51.     int ab_diff;
    
52. 
    
53.     ab_diff = abs(sum(a)-sum(b));
    
54.     for (i=0; i<N; i++){
    
55.         for (j=0; j<N; j++){
    
56.             change(a+i, b+j);
    
57.             if (abs(sum(a)-sum(b)) < ab_diff){//判断是否需要交换元素
    
58.                 is_swap = 1; //置位交换标志
    
59.                 ab_diff = abs(sum(a)-sum(b)); //更新差值
    
60.             }
    
61.             else{
    
62.                 change(b+j, a+i);//不交换
    
63. 
    
64.             }
    
65.         }
    
66.     }
    
67.     return is_swap;
    
68. }
    
69. int main(){
    
70. 
    
71.     int a[N];
    
72.     int b[N];
    
73. 
    
74.     ary_init(a,b);//数组元素初始化
    
75.     prt_ary(a, b);//列印当前数组状态
    
76.     while (slove(a, b));//处理数组
    
77.     prt_ary(a, b);//列印交换后数组状态
    
78.     getch();
    
79. }
    

复制代码

[ 本帖最后由 greensky_34 于 2006-11-14 21:20 编辑 ]

cuicp

原帖由 xmyth 于 2006-11-14 20:44 发表
这个结束条件应该是没有问题的

在你说的这个例子里，已经满足了我所提出的结束条件

前面我假设了A>0 (如果A不大于0，对换一下就好了)

所以这里a = {1,2,12}; b = {4,5,3};

x=a-b[j]

所有的x ...

哦，明白了，如果(sum(a) - sum(b)) > (a -b[j]) > 0的话，也就是数组a的和比数组b的和大，
而数组b中有比数组a中小的元素，如果把a和b[j]交换，就可以把数组a和数组b的差缩小，又因为
(sum(a) - sum(b)) > (a -b[j]) ，所以交换后不会出现sum(a) < sum(b)的情况。这样循环调整后，
当整体上sum(a)  > sum(b))时，局部上（数组元素）无法交换了，也就是无法找到符合条件的x了。

呵呵，本人天生比较笨，要想一想才能明白！

谢谢xmyth的解释！