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

lih928

原我犯了很多數(shù)人一樣的錯(cuò)誤

主觀一定認(rèn)為最大的兩個(gè)數(shù)一定要分開

[ 本帖最后由 lih928 于 2006-11-17 16:46 編輯 ]

tyc611

1. 原帖由 [i]xmyth[/i] 于 2006-11-14 17:04 發(fā)表
   
2. 當(dāng)前數(shù)組a和數(shù)組b的和之差為
   
3. A = sum(a) - sum(b)
   
4. 
   
5. a的第i個(gè)元素和b的第j個(gè)元素交換后，a和b的和之差為
   
6. A' = sum(a) - a[i] + b[j] - (sum(b) - b[j] + a[i])
   
7.        = sum(a) - sum(b) - 2 (a[i] - b[j]) ...

復(fù)制代碼

當(dāng)x 在 (0,A)之間時(shí)，做這樣的交換才能使得交換后的a和b的和之差變小，x越接近A/2效果越好, 如果找不到在(0,A)之間的x，則當(dāng)前的a和b就是答案。

當(dāng)這樣的X不存在時(shí)，并不能結(jié)束算法。還可能存在如下情形，可以得到更小的差值：
例如： A=｛3， 5， 6， 7， 13， 14｝
       B=｛1， 3， 7， 8， 10， 17｝
此時(shí)有，sum(A) - sum(B) = 2 ，并且不存在（0， 2）之間的x值。
但將A中的5和6與B中的3和7同時(shí)交換，得到
       A=｛3， 3， 7， 7， 13， 14｝
       B=｛1， 5， 6， 8， 10， 17｝
此時(shí)有：sum(A) - sum(B) = 0，此時(shí)的數(shù)組才是解。

我覺得這個(gè)算法難在如何有效尋找a(i)]和b[j]上

[ 本帖最后由 tyc611 于 2006-11-17 23:54 編輯 ]

tyc611

>為啥上邊的回復(fù)后部分斜了呢

1. 知道了，原來是a[i]中的[i]在作祟:em02:

復(fù)制代碼

[ 本帖最后由 tyc611 于 2006-11-17 23:58 編輯 ]

天狼星

建2各數(shù)組,把那些數(shù)從大到小,分別放入數(shù)組就成把.   放的時(shí)候判斷一下就行了.
if (sum(a)>sunm(b))
  a.push_back(num)
else
  b.push_back(num)

dourt

xmyth 兄從事什么專業(yè)?
能夠快速的把實(shí)際問題模式化,并行成正確的數(shù)學(xué)思維,論證嚴(yán)謹(jǐn).
而且整個(gè)模型具有智能的味道,佩服佩服
令我收益非淺那~~

svenwang

1. 
   
2. int abs(int n)
   
3. {
   
4.         return n >= 0 ? n : -n;
   
5. }
   
6. 
   
7. int sum(int *array, int count)
   
8. {
   
9.         int sum = 0;
   
10.         for (int i = 0; i < count; i++)
    
11.                 sum += array[i];
    
12.         return sum;
    
13. }
    
14. 
    
15. void exchange(int *array1, int *array2, int count)
    
16. {
    
17.         int sum1 = sum(array1, count);
    
18.         int sum2 = sum(array2, count);
    
19.         if (sum1 == sum2)
    
20.                 return;
    
21.                
    
22.         int diff = abs(sum1 - sum2);
    
23.         for (int i = 0; i < count; i++) {
    
24.                 for (int j = 0; j < count; j++) {
    
25.                         int s1 = sum1 + array2[j] - array1[i];
    
26.                         int s2 = sum2 + array1[i] - array2[j];
    
27.                         if (abs(s1 - s2) < diff) {
    
28.                                 int tmp = array1[i];
    
29.                                 array1[i] = array2[j];
    
30.                                 array2[j] = tmp;
    
31.                                 sum1 = s1;
    
32.                                 sum2 = s2;
    
33.                                 diff = abs(sum1 - sum2);
    
34.                                 if (diff == 0)
    
35.                                         return;
    
36.                         }
    
37.                 }
    
38.         }
    
39. }
    

復(fù)制代碼

[ 本帖最后由 svenwang 于 2006-11-17 23:41 編輯 ]

slsl8460

先把數(shù)據(jù)放到一個(gè)臨時(shí)數(shù)組中，排序且求和sum；用背包算法，盡量是一個(gè)數(shù)組大小為n的存放的數(shù)字和為sum／2

emacsnw

原帖由 slsl8460 于 2006-11-17 19:09 發(fā)表
先把數(shù)據(jù)放到一個(gè)臨時(shí)數(shù)組中，排序且求和sum；用背包算法，盡量是一個(gè)數(shù)組大小為n的存放的數(shù)字和為sum／2

原題說了數(shù)組里面元素的值任意，背包算法的效率線性于最大容積K，這里就是sum/2，如果這個(gè)數(shù)字可以任意，那背包算法也沒什么意義了。

海濱

關(guān)注．．．．

geba168

搞一個(gè)數(shù)組C   包含了全部a  b  的數(shù)據(jù)   并排序（再生成C的時(shí)候就排序）
然后在C里面  選1個(gè) 放到A  第2n個(gè)放到B  第2個(gè)放到A  第2n-1個(gè)放到B。。。。。。。

[ 本帖最后由 geba168 于 2006-11-18 22:23 編輯 ]