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

matin_mo

整体排序，然后交叉取数，每次把大数放入和比较小的那个数组里面。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARRAY_SIZE 10

void generate_n(int *a, int num)
{
    int i = 0;

    for(i = 0 ; i < num; i++)
        a[i] = rand() % 1000;

}

int sum_n(int *a, int num)
{
    int i = 0, result = 0;
    for(i = 0 ; i < num; i++)
        result += a[i];

    return result;

}

void print_n(int *a, int num){
    int i =0;
    for(i = 0; i< num; i++)
         printf("%d  ",a[i]);
    printf("\n");
}

int cmp(int *a, int *b)
{
        if (*a < *b)
            return 1;
        if(*a > *b)
                return -1;
        return 0;

}

int main(){

    int a[ARRAY_SIZE];
    int b[ARRAY_SIZE];

    int c[ARRAY_SIZE *2];
    int i= 0;
    int *max = 0;
    int *min = 0;

    int count = 0;
    srand(time(NULL));
    generate_n(a,ARRAY_SIZE);
    generate_n(b,ARRAY_SIZE);

    printf("a is ");
    print_n(a,ARRAY_SIZE);

    printf("b is ");
    print_n(b,ARRAY_SIZE);

    printf("sum of a is %d\n", sum_n(a,ARRAY_SIZE));
    printf("sum of b is %d\n", sum_n(b,ARRAY_SIZE));


    printf("absolute of (sum(a) - sum(b)) is %d\n", abs(sum_n(a,ARRAY_SIZE) - sum_n(b,ARRAY_SIZE)));

    memcpy(c, a, ARRAY_SIZE*sizeof(int));
    memcpy(c+ARRAY_SIZE, b, ARRAY_SIZE*sizeof(int));

    printf("c is ");
    print_n(c,ARRAY_SIZE * 2);


    qsort(c, ARRAY_SIZE*2,  sizeof(int),cmp);

    printf("c is ");
    print_n(c,ARRAY_SIZE * 2);

    max = a;
    min = b;

    for(i = 0; i < ARRAY_SIZE * 2; i+=2){
        *max = c[i];
        *min = c[i+1];
        count ++;
        if(sum_n(a,count) >= sum_n(b,count)){
            max = &b[count];
            min = &a[count];
        }
        else{
            max = &a[count];
            min  = &b[count];
        }
    }

    printf("a is ");
    print_n(a,ARRAY_SIZE);

    printf("b is ");
    print_n(b,ARRAY_SIZE);

    printf("sum of a is %d\n", sum_n(a,ARRAY_SIZE));
    printf("sum of b is %d\n", sum_n(b,ARRAY_SIZE));


    printf("absolute of (sum(a) - sum(b)) is %d\n", abs(sum_n(a,ARRAY_SIZE) - sum_n(b,ARRAY_SIZE)));

    return 0;

}

thefirstz

算法描述：分别排序两个数组，取出较小数组中第一个元素(最小元素)x，然后寻找和较大数组中第一个比x大的元素y，
然后用y去交换和较小数组中小于y且最接近y的元素，使得每次的和改变为最小，直到两个数组和的差额不能缩小为止。

1. #define SWAP(x,y)   {int t = (x);(x)=(y);(y)=t;}
   
2. 
   
3. int partition(int k[], int size){
   
4.     int x = k[size-1];
   
5.     int i = 0;
   
6.     int j = 0;
   
7.     while(i < size){
   
8.         if(k[i]<x) { SWAP(k[i],k[j]); ++j;  }
   
9.         ++i;
   
10.     }
    
11.     SWAP(k[j],k[size-1]);
    
12.     return j;
    
13. }
    
14. 
    
15. void quickSort(int k[], int size){
    
16.     if(size < 2)    return;
    
17.     int mid = partition(k,size);
    
18.     quickSort(k,mid);
    
19.     quickSort(k+mid+1,size-mid-1);
    
20. }
    
21. 
    
22. int getMinDiff(int k1[], int size1, int k2[], int size2){
    
23.     int oldDiff = 0;
    
24.     int newDiff = 0;
    
25.     int index = 0;
    
26.     int sum1 = 0;
    
27.     int sum2 = 0;
    
28. 
    
29.     for(index=0; index<size1; ++index){
    
30.         sum1 += k1[index];
    
31.     }
    
32.     for(index=0; index<size2; ++index){
    
33.         sum2 += k2[index];
    
34.     }
    
35.     oldDiff = abs(sum1 - sum2);
    
36.     newDiff = oldDiff;
    
37. 
    
38.     while(newDiff <= oldDiff){
    
39.         quickSort(k1,size1);
    
40.         quickSort(k2,size2);
    
41. 
    
42.         int minIndex;
    
43.         int j;
    
44.         if(sum1 < sum2){
    
45.             minIndex = 0;
    
46.             j = 0;
    
47.             while(k1[minIndex] >= k2[j] && j<size2)    ++j;
    
48.             while(k1[minIndex] < k2[j] && minIndex<size1) ++minIndex;
    
49.             --minIndex;
    
50.             SWAP(k1[minIndex],k2[j]);
    
51.         } else{
    
52.             minIndex = 0;
    
53.             j = 0;
    
54.             while(k2[minIndex] >= k1[j] && j<size1)    ++j;
    
55.             while(k2[minIndex] < k1[j] && minIndex<size2) ++minIndex;
    
56.             --minIndex;
    
57.             SWAP(k2[minIndex],k1[j]);
    
58.         }
    
59.         sum1 = 0;
    
60.         sum2 = 0;
    
61.         for(index=0; index<size1; ++index){
    
62.             sum1 += k1[index];
    
63.         }
    
64.         for(index=0; index<size2; ++index){
    
65.             sum2 += k2[index];
    
66.         }
    
67.         oldDiff = newDiff;
    
68.         newDiff = abs(sum1 - sum2);
    
69.         if(newDiff == oldDiff)  break;
    
70.     }
    
71. 
    
72.     return oldDiff;
    
73. }
    
74. 
    
75. int main()
    
76. {
    
77.     int k1[3] = {1,3,2};
    
78.     int k2[4] = {0,0,4,100};
    
79.     int d = getMinDiff(k1,3,k2,4);
    
80.     printf("%d\n",d);
    
81. 
    
82.     return 0;
    
83. }

复制代码

Perlvim

应当是差的绝对值最小，否则就好办了

sendry915

回复 13# ccjjhua


从最大到最小排列更加正确...
   
把a,b 2数组的元素放到数组3（2n大小） 中进行排序，
a 先取最大的，b先取次大的，
然后根据a,b已取元素和的大小来决定谁来取剩下元素中最大的。策略是，已取得的所有元素之和小的来取C中剩下元素中的最大者。如此反复，直到取完。每次都是a,b各取一个。

x5miao

问题是是否需要保证A，B两数组的元素个数相同。

这个问题就和去买火车票或者银行柜台前排队的时候，如何选择一个等待时间最短的队伍的过程是差不多的。

sh365

chzht001 发表于 2006-11-14 10:36
先将数组排序（全排序，两个数组一起排），然后类似如下处理

#include   

这个swap函数有个隐含bug，如果x == y != 0, 则swap(&x, &y)后，x=0了。

一个人取暖

可以肯定, 通过排序然后划分集合的方法绝对是错的. 动态规划靠谱.

一个人取暖

hongyunqi 发表于 2010-08-02 01:15
哎，实在是看不下这又臭又长的讨论帖了。

首先一点，在讨论到交换数据以达到整体差值最小时

我也这么认为, 当多个数据交换的时候, 根本不可能通过简单的交换就行.

wangzhen11aaa

我觉得 全部排序（可以考虑用quicksort）。
最小数和最大数在一个数组内没有异议吧。
那么第n较小数和第n较大数是否在相同的数组
就看前面的差值有多大了。



最终结果不一定唯一。让人纠结的在于 如果最后两个数组和只差1，还要找到所有不为0的情况。

btdm123

类似游标卡尺，一把长度为2n的尺上，有一个长度为n的游标在移动