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

hgmyjr

既然是最小肯定包括差值为负数.所以可以搜索两个数组到临时数组中[2n],然后排序小端放入A,大端放入B.

xzw077

没有简单的方法 应该会用到背包算法。8分钟 呵呵 你去叫F1
的兄弟出来做做看有几个人能搞定：）

epegasus

都这么久了早被华为淘汰了

lknh17

哈哈，不过这是在哪面试的，华为来我们学校似乎不出什么现场编程的题
而且华为工资不知道怎么给的，看学校BBS上，同是本科生有的3K，有5.5K，很怪啊

mu_mu8309

我个人认为是对两个数组分别排序,然后计算每个数组的和,那数组的和大的数组的小的数和数组的和小的数组的 大的数交换,比如数组A的和比数组B的和大,就那B中的小数和A中的大数交换,然后在比较,在交换.......
呵呵,可能说的还是不太清楚,我的表达能力不好

toplee

从头到尾看了一遍，得到启发，不过至今楼主也没有公布正确结果，我也尝试搞了一个，考虑到数组处理和打印显示的方便，懒得用c来写这段代码，尝试用PHP来写了一段，经过各种测试案例没有发现失败。
代码如下：

1. 
   
2. <?php
   
3. 
   
4. //下面列举了三种前面常提到的特殊例子和一个通常情况下的数组例子，均进行了测试
   
5. $a = array(1,0,3);
   
6. $b = array(1,2,20);
   
7. 
   
8. $a = array(3,5,6,7,13,14);
   
9. $b = array(1,3,7,8,10,17);
   
10. 
    
11. $a = array(11,12,8,91);
    
12. $b = array(1,2,17,100);
    
13. 
    
14. $a = array(1,7,3,343,43,23,2323,454,5,5656,56,565,43,41,23,2,0,0,1);
    
15. $b = array(10,15,4,454,45,76,787,989,67,4545,65,566,2,343,3,4,2,4,0);
    
16. 
    
17. $count = count($a);
    
18. 
    
19. $c = array_merge($a,$b);
    
20. sort($c);
    
21. $sum = array_sum($c);
    
22. $max = $c[$count*2-1];
    
23. 
    
24. if ($max >= $sum/2) { //如果有一个数字大于其他数字总和，简单处理
    
25.     for($i=0;$i<($count-1);$i++) {
    
26.         $a[$i] = $c[$i];
    
27.         $b[$i] = $c[$count-1+$i];
    
28.     }
    
29.     $a[$count-1] = $max;
    
30.     $b[$count-1] = $c[$count*2-2];
    
31. 
    
32. } else {    //通常情况
    
33. 
    
34.     for ($i=0;$i<$count;$i++) {
    
35.         $suma = array_sum($a);
    
36.         $sumb = array_sum($b);
    
37.         
    
38.         $x = ($suma - $sumb)/2; //两个数组各自和的差
    
39.         $min = abs($x);    //差的绝对值
    
40.         
    
41.         $ch = false;    //进行交换的开关
    
42.         $t = 0;
    
43.                
    
44.         for ($j=0;$j<$count;$j++) {
    
45.             $y = ($a[$i] - $b[$j]); //两个元素间的差
    
46.             $z = $x-$y;     //数组和之差与元素差之间的差，不考虑正负
    
47.             $absz = abs($z);    //得到绝对值，用绝对值比较
    
48.             
    
49.             if ($absz <= $min) {
    
50.                 $ch = true;
    
51.                 $min = $absz;
    
52.                 $t = $j;
    
53.             }
    
54.         }
    
55.         
    
56.         if ($ch) {  //找到$ai和$bj，进行交换
    
57.             $tmp = $a[$i];
    
58.             $a[$i] = $b[$t];
    
59.             $b[$t] = $tmp;
    
60.         }
    
61.     }
    
62. 
    
63. }
    
64. 
    
65. sort($a);
    
66. sort($b);
    
67. 
    
68. //分别打印输出重新分组后的$a和$b数组，以及各自的和
    
69. echo "Sum(b) = ".array_sum($a)."\n";
    
70. print_r($a);
    
71. 
    
72. echo "Sum(b) = ".array_sum($b)."\n";
    
73. print_r($b);
    
74. 
    
75. ?>
    

复制代码

其实我的解题思路很简单：首先这道题可以认为是把2n个数进行均分成两组数，要求两组数的和尽可能接近。
从楼主的题目中可以看出，排序应该不是主要的，而如何进行交换是非常重要的，关键的就是ai和bj的确定问题。

这个里面可能会有两种情况，一种是所有的数字当中，有一个数字大于其他数字总和，这种情况很好处理，把2n个数字里面最小的0,n-2个加上最大的那个数字给a数组，剩下的为b数组即可，另外一种情况就是通常情况，没有一个数字绝对大。

[ 本帖最后由 toplee 于 2006-11-23 15:32 编辑 ]

agaonet

原帖由 la.lune 于 2006-11-13 10:55 发表
放到一个临时数组里排序后，两头取，分别存在a,b里

同意~ [/quote]

我也同意.

合并放到一个临时的数组里边,排序列.然后在分别交替取头尾.依次交替放往a,b数组.即:

取头,取尾.放往a.
取[头-1],取[尾-1].放b.
取[头-2],取[尾-2].放a.
取[头-3],取[尾-3].放b.
.........

这样永远A大于B..并且两数组之间最相等.

[ 本帖最后由 agaonet 于 2006-11-28 20:26 编辑 ]

chaiking

我也想一个，
a) 两个数组合并c[n],然后从小到大排列，
b) 新建两个空数组， 第一大c[n]放在a[1],第二大c[n-1] 放在b[1]
c) 接下去就是递归了，c[i] (i从后面开始)放在 min(a数组之和 ,b数组之和) 之中.
d) 结束
{1,2,3} {0,0,999}->{0,0,1,2,3,999}
a[1]=999,b[1]=3;
b[2] =2,
b[3]=1
b[4]=0;
b[5]=0;

chaiking

// huawei.cpp : 定义控制台应用程序的入口点。
//某面试题，自己测试
/*
有两个数组a,b，大小都为n,数组元素的值任意，无序；
要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小
*/

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int min(vector<int> a1,vector<int> b1)
{
        int sum1 = 0;
        int sum2 = 0;
       
        vector<int>::const_iterator Siter;

        for(Siter = a1.begin(); Siter != a1.end(); ++Siter)
                sum1 += *Siter;
        for(Siter = b1.begin(); Siter != b1.end(); ++Siter)
                sum2 += *Siter;

        if(sum1 < sum2) return 1;
        else return 0;

       

}
int _tmain(int argc, _TCHAR* argv[])
{
        int a[6] = {3,5,6,7,13,14};
        int b[6] = {1,3,7,8,10,17};
        vector<int> a1;
        vector<int> b1;
        vector<int> c1;

        vector<int>::const_iterator iter;
        int i;

        for(i=0; i<6; i++)
                c1.push_back(a[i]);
        for(i=0; i<6; i++)
                c1.push_back(b[i]);


        sort( c1.begin( ), c1.end( ), greater<int>( ) );

        for(iter = c1.begin(); iter != c1.end() ; ++iter)
                cout<<*iter<<',';
       
       
        iter = c1.begin();
        a1.push_back(*iter);
        b1.push_back(*(++iter));
       
        for(; iter != c1.end(); ++iter)
        {
                if(min(a1,b1))
                        a1.push_back(*iter);
                else b1.push_back(*iter);
        }
       
        cout<<"\na1 :\n ";
        for(iter = a1.begin(); iter != a1.end(); ++iter)
                cout<<*iter<<',';
        cout<<"\nb1 :\n ";
        for(iter = b1.begin(); iter != b1.end(); ++iter)
                cout<<*iter<<',';
}

lnfxcf

把所有的数取出来，按照从大小进行排列，放在数组c。
a和b分别由totalA totalB累计分别的和（初值为0）。
顺序从c之中取两个数，把较大的数放在total较小的数足里。
over