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

hongyunqi

哎，实在是看不下这又臭又长的讨论帖了。

首先一点，在讨论到交换数据以达到整体差值最小时
既要考虑交换单个数据，也要考虑同时交换两个，三个。。。数据
想一下 一组里有 5，7 另一组里有 1， 10，单个差值最小都是10-7=3，但是加起来5+7-1+10=11最小是1
这样一来的话
不就成了NP问题了吗

这样讨论还有意义吗

sumland

看完了所有的回帖，我最后一个回帖

zmywly8866

将两个数组并在一起升序排序后，交叉取值，即第奇数个数放在一个数组中，第偶数个数放在另一个数组中，然后计算每个数组的和再相减。因为排序后相邻两个数字相差上最小的，这是我的认为：

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. 
   
5. void
   
6. main ()
   
7. {
   
8.   int arr[5] = { 1, 5, 10, 3, 8 };
   
9.   int brr[5] = { 2, 4, 3, 6, 9 };
   
10.   int index, jndex, temp, t, crr[10];
    
11.   for (index = 0; index < 10; index++)
    
12.     {
    
13.       if (index < 5)
    
14.         {
    
15.           crr[index] = arr[index];
    
16.         }
    
17.       else
    
18.         {
    
19.           crr[index] = brr[index - 5];
    
20.         }
    
21.       //printf ("%d\t", crr[index]);
    
22.     }
    
23.   //printf ("\n");
    
24. 
    
25.   for (index = 0; index < 10; index++)
    
26.     {
    
27.       for (jndex = 0; jndex < index; jndex++)
    
28.         {
    
29.           if (crr[index] <= crr[jndex])
    
30.             {
    
31.               temp = crr[index];
    
32.               crr[index] = crr[jndex];
    
33.               crr[jndex] = temp;
    
34.             }
    
35.         }
    
36.     }
    
37. 
    
38. #if 0
    
39.   for (index = 0; index < 10; index++)
    
40.     {
    
41.       printf ("%d\t", crr[index]);
    
42.     }
    
43.   printf ("\n");
    
44. 
    
45. #endif
    
46.   for (index = 0; index < 10; index += 2)
    
47.     {
    
48.       arr[index / 2] = crr[index];
    
49.       brr[index / 2] = crr[index + 1];
    
50.     }
    
51. 
    
52. #if 0
    
53.   for (index = 0; index < 5; index++)
    
54.     {
    
55.       printf ("%d\t", arr[index]);
    
56.     }
    
57.   printf ("\n");
    
58.   for (index = 0; index < 5; index++)
    
59.     {
    
60.       printf ("%d\t", brr[index]);
    
61.     }
    
62.   printf ("\n");
    
63. 
    
64. #endif
    
65.   t = 0;
    
66.   for (index = 0; index < 5; index++)
    
67.     {
    
68.       t += (brr[index] - arr[index]);
    
69.     }
    
70.   printf ("The result is %d\n", t);
    
71. }
    

复制代码

测试：

myz@ubuntu:~$ gcc test.c -o test
myz@ubuntu:~$ ./test
The result is 5

cjaizss

乘方级别算法,关键还不是NP

cjaizss

算法很简单,就是试过所有组合,找个最接近的,套进去搞定

cjaizss

面试官说了不能用枚举
forrestgang 发表于 2006-11-13 13:59

    面试官就一白痴,典型的乘方级别算法,通用情况下无更好算法,比NPC更复杂

kenny_cplus

1. 将数组放到一个临时数组中。
2. 对临时数组中的元素进行排序
3. 将数组a和b清零
4. 遍历临时数组中的每两个元素
5. 对两数组求和，将小的元素分配给和较大的数组

1. #include<iostream.h>
   
2. int get_sum(int* p);
   
3. int get_min(int a,int b);
   
4. int get_max(int a,int b);
   
5. int main()
   
6. {
   
7.         int a[5]={5,4,5,9,2};
   
8.     int b[5]={5,2,7,2,4};
   
9.         int temp[10]={0};
   
10.         for(int i=0;i<5;i++)
    
11.                 temp[i]=a[i];
    
12.         for(int j=0;j<5;j++)
    
13.                 temp[j+5]=b[j];
    
14.        
    
15.         for(int n=10;n>0;n--)
    
16.                 for(int m=0;m<n-1;m++)
    
17.                 {
    
18.                         if(temp[m]>temp[m+1])
    
19.                         {
    
20.                                 int tran=0;
    
21.                                 tran=temp[m];
    
22.                                 temp[m]=temp[m+1];
    
23.                                 temp[m+1]=tran;
    
24.                         }
    
25.                 }
    
26.                 for(int x=0;x<5;x++)
    
27.                 {
    
28.                         a[x]=0;
    
29.                         b[x]=0;
    
30.                 }
    
31.                
    
32.                 for(int t=0;t<10;t=t+2)
    
33.                 {
    
34.                         int* pa=a;
    
35.                         int* pb=b;
    
36.                         int sum_a=get_sum(pa);
    
37.                         int sum_b=get_sum(pb);
    
38.                         if(sum_a>=sum_b)
    
39.                         {
    
40.                                 a[t/2]=get_min(temp[t],temp[t+1]);
    
41.                                 b[t/2]=get_max(temp[t],temp[t+1]);
    
42.                         }
    
43.                         else
    
44.                         {
    
45.                                 a[t/2]=get_max(temp[t],temp[t+1]);
    
46.                                 b[t/2]=get_min(temp[t],temp[t+1]);
    
47.                         }
    
48.                        
    
49.                 }
    
50.                
    
51.                 cout<<"a数组为：";
    
52.                 for(int k=0;k<5;k++)
    
53.                 {
    
54.                         cout<<a[k]<<"\t";
    
55.                 }
    
56.                 cout<<endl;
    
57.                 cout<<"b数组为：";
    
58.                 for(int q=0;q<5;q++)
    
59.                 {
    
60.                         cout<<b[q]<<"\t";
    
61.                 }
    
62.                 cout<<endl;
    
63.                
    
64.                 return 0;
    
65. }
    
66. 
    
67. 
    
68. int get_sum(int* p)
    
69. {
    
70.         int i=1;
    
71.         int sum=0;
    
72.         while(i<=5)
    
73.         {
    
74.                 sum+=*p;
    
75.                 p++;
    
76.                 i++;
    
77.         }
    
78.         return sum;
    
79. }
    
80. 
    
81. int get_min(int a,int b)
    
82. {
    
83.         if(a<=b)
    
84.                 return a;
    
85.         else
    
86.                 return b;
    
87. }
    
88. 
    
89. int get_max(int a,int b)
    
90. {
    
91.         if(a<=b)
    
92.                 return b;
    
93.         else
    
94.                 return a;
    
95. }

复制代码

sunshitaolang

我的一点想法 先把两个数组组合在一起，然后按顺序排列，接着求出任意两个相邻的数之间的差，然后取差最小的两个数，再计算剩下的数的相邻两数的差，再取最小的，一直循环，一点见解

gyarenas

嗯，感觉是动态规划，子问题的重叠形是肯定有的，还要分析一下最有子结构和求法

iphonebabe

呵呵，这种题目很基础的