華為面試題(8分鐘寫出代碼)

hgmyjr

既然是最小肯定包括差值為負(fù)數(shù).所以可以搜索兩個數(shù)組到臨時數(shù)組中[2n],然后排序小端放入A,大端放入B.

xzw077

沒有簡單的方法 應(yīng)該會用到背包算法。8分鐘 呵呵 你去叫F1
的兄弟出來做做看有幾個人能搞定：）

epegasus

都這么久了早被華為淘汰了

lknh17

哈哈，不過這是在哪面試的，華為來我們學(xué)校似乎不出什么現(xiàn)場編程的題
而且華為工資不知道怎么給的，看學(xué)校BBS上，同是本科生有的3K，有5.5K，很怪啊

mu_mu8309

我個人認(rèn)為是對兩個數(shù)組分別排序,然后計算每個數(shù)組的和,那數(shù)組的和大的數(shù)組的小的數(shù)和數(shù)組的和小的數(shù)組的 大的數(shù)交換,比如數(shù)組A的和比數(shù)組B的和大,就那B中的小數(shù)和A中的大數(shù)交換,然后在比較,在交換.......
呵呵,可能說的還是不太清楚,我的表達(dá)能力不好

toplee

從頭到尾看了一遍，得到啟發(fā)，不過至今樓主也沒有公布正確結(jié)果，我也嘗試搞了一個，考慮到數(shù)組處理和打印顯示的方便，懶得用c來寫這段代碼，嘗試用PHP來寫了一段，經(jīng)過各種測試案例沒有發(fā)現(xiàn)失敗。
代碼如下：

1. 
   
2. <?php
   
3. 
   
4. //下面列舉了三種前面常提到的特殊例子和一個通常情況下的數(shù)組例子，均進(jìn)行了測試
   
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) { //如果有一個數(shù)字大于其他數(shù)字總和，簡單處理
    
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; //兩個數(shù)組各自和的差
    
39.         $min = abs($x);    //差的絕對值
    
40.         
    
41.         $ch = false;    //進(jìn)行交換的開關(guān)
    
42.         $t = 0;
    
43.                
    
44.         for ($j=0;$j<$count;$j++) {
    
45.             $y = ($a[$i] - $b[$j]); //兩個元素間的差
    
46.             $z = $x-$y;     //數(shù)組和之差與元素差之間的差，不考慮正負(fù)
    
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，進(jìn)行交換
    
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數(shù)組，以及各自的和
    
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. ?>
    

復(fù)制代碼

其實我的解題思路很簡單：首先這道題可以認(rèn)為是把2n個數(shù)進(jìn)行均分成兩組數(shù)，要求兩組數(shù)的和盡可能接近。
從樓主的題目中可以看出，排序應(yīng)該不是主要的，而如何進(jìn)行交換是非常重要的，關(guān)鍵的就是ai和bj的確定問題。

這個里面可能會有兩種情況，一種是所有的數(shù)字當(dāng)中，有一個數(shù)字大于其他數(shù)字總和，這種情況很好處理，把2n個數(shù)字里面最小的0,n-2個加上最大的那個數(shù)字給a數(shù)組，剩下的為b數(shù)組即可，另外一種情況就是通常情況，沒有一個數(shù)字絕對大。

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

agaonet

原帖由 la.lune 于 2006-11-13 10:55 發(fā)表
放到一個臨時數(shù)組里排序后，兩頭取，分別存在a,b里

同意~ [/quote]

我也同意.

合并放到一個臨時的數(shù)組里邊,排序列.然后在分別交替取頭尾.依次交替放往a,b數(shù)組.即:

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

這樣永遠(yuǎn)A大于B..并且兩數(shù)組之間最相等.

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

chaiking

我也想一個，
a) 兩個數(shù)組合并c[n],然后從小到大排列，
b) 新建兩個空數(shù)組， 第一大c[n]放在a[1],第二大c[n-1] 放在b[1]
c) 接下去就是遞歸了，c[i] (i從后面開始)放在 min(a數(shù)組之和 ,b數(shù)組之和) 之中.
d) 結(jié)束
{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 : 定義控制臺應(yīng)用程序的入口點(diǎn)。
//某面試題，自己測試
/*
有兩個數(shù)組a,b，大小都為n,數(shù)組元素的值任意，無序；
要求：通過交換a,b中的元素，使數(shù)組a元素的和與數(shù)組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

把所有的數(shù)取出來，按照從大小進(jìn)行排列，放在數(shù)組c。
a和b分別由totalA totalB累計分別的和（初值為0）。
順序從c之中取兩個數(shù)，把較大的數(shù)放在total較小的數(shù)足里。
over