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

北河东林

ccjjhua 发表于 2006-11-13 11:42
把a,b 2数组的元素放到数组3（2n大小） 中进行排序，
a 先取最小的，b先取次小的，
然后根据a,b已取元素和 ...

同意此楼的算法

长生不老的萝卜

我觉着这个和用天秤称某样物体的重量是一样的，a[],b[]数组中元素合为一组sum[],sum/2是我们要称的重量，把它放入左盘，然后向右盘放砝码，先放最大的，再放次大的，最后放小的,比如：
3,6,7,9,21
sun/2=46/2=23
所以先放21，有21<23,差值为2，放入最接近2的，即sum[i]-2取最小值，这是需要遍历一下总数组，然后放入3，21+3>23,完毕，剩下的放一堆
刚才21与23差值为2，其实，我们可以根据这个差值来确定遍历时用二分法还是其他的从头查找或倒着查找，以上！！

232319779

#include <stdio.h>
#include <STDLIB.H>
#include <time.h>

#define N 10

int f(int *a,int *b);

int main(int argc, char* argv[])
{
        int a[N] ={0};
        int b[N] = {0};
        int c[N + N] = {0};
        int i = 0;

        srand( (unsigned)time( NULL ) );
       
        for (i = 0;i < N;i++)
        {
                a[i] = rand() % 100;
                b[i] = rand() % 100;
                c[i] = a[i];
                c[i + N] = b[i];
        }

        for(i = 0;i < N + N;i++)
        {
                int temp;
                for (int j = i;j < N + N;j++)
                {
                        if (c[i] > c[j])
                        {
                                temp = c[i];
                                c[i] = c[j];
                                c[j] = temp;
                        }
                }
        }
       
        for(i = 0;i < N;i++)
        {
                a[i] = c[i];
                b[i] = c[i + N];
        }

        int r = f(a,b);

        printf("%d\n",r);
       
        for(i = 0;i < N;i++)
        {
                printf("%3d",a[i]);
        }
        printf("\n");
       
        for(i = 0;i < N;i++)
        {
                printf("%3d",b[i]);
        }
        printf("\n");
        return 0;
}

void f1(int &a,int &b)
{
        int temp;
       
        temp = a;
        a = b;
        b = temp;
}

int f(int *a,int *b)
{
        int result;
        int min;
        int aa,bb;
        int i = 0,j = 0;

        aa = 0;
        bb = 0;
        for (i = 0;i < N ;i++)
        {
                aa += a[i];
                bb += b[i];
        }

        min = abs(aa - bb);
        for (i = N - 1;i >= 0;i--)
        {                       
                aa -= a[i];
                bb -= b[i];
                f1(a[i],b[i]);
                aa += a[i];
                bb += b[i];

                result = abs(aa - bb);
                if(min > result)
                {
                        min = result;
                }
                else
                {
                        f1(a[i],b[i]);
                        break;
                }

        }
        return min;
}

232319779

a全部给最小的，b全部给最大的。依次对换。

caseboy01

把所有的数字从大到小排序，然后最大的分给数组a, 第二个分给数组b，然后后面的数字根据俩个数组的大小分，第三个数字分给数组b，再比较a,b大小， b大就把第4个数字给a，b小就把第四个数字给b（判断b的数目是不是==n，等于n就把后面的数字都给a）， 后面的数字就根据第四个数字这样分配。 没代码

shaneqi

如果能给大家带来好处也不错。

Lzz_sg

回复 341# 长生不老的萝卜
恩，这个方法不错


   

_Rayx

回复 341# 长生不老的萝卜


错误：）
2 2 4 4 6 6

你的方法：先放6，再放6，剩下是2 2 4 4，但是要求是每个组个数一样，所以还要再放一个，就算最小也是2，两组为6 6 2 ， 4 4 2, 结果错误。

江南书匠

不才，也小写了一段代码，耗时远不止8分钟
思路和前面各位差不多，也没想到更好的方法，时间复杂度O(n)，空间复杂度O(n).

1. #include <cstdlib>
   
2. #include <iostream>
   
3. #include <ctime>
   
4. #include <cmath>
   
5. 
   
6. using namespace std;
   
7. #define N 16                // The length of the array
   
8. 
   
9. int intCmp(const void *p, const void *q)
   
10. {
    
11.         return (*(int *)p - *(int *)q);
    
12. }
    
13. 
    
14. void findTheLeastGap(int *pArr1, int *pArr2)
    
15. {
    
16.         int *pArr3 = new int[2 * N];
    
17.         int i, j1, j2;
    
18. 
    
19.         qsort((void *)pArr1,(size_t)N, sizeof(int), intCmp);   // sort the array
    
20.         qsort((void *)pArr2, (size_t)N, sizeof(int), intCmp);
    
21. 
    
22.         for (i = 0, j1 = 0, j2 = 0; i < 2 * N; i++)                  // merge the arrays to the temp array
    
23.         {
    
24.                 if ((j1 == N)
    
25.                         || ((j2 != N) && (pArr1[j1] > pArr2[j2])))
    
26.                 {
    
27.                         pArr3[i] = pArr2[j2];
    
28.                         j2++;
    
29.                 }
    
30.                 else
    
31.                 {
    
32.                         pArr3[i] = pArr1[j1];
    
33.                         j1++;
    
34.                 }
    
35.         }
    
36. 
    
37.         int cnt1 = 0, cnt2 = 0;
    
38. 
    
39.         for (i = 0, j1 = 0, j2 = 0; (i < 2 * N) && (j1 <N) && (j2 < N); i+=2)     // adjust the array one by one
    
40.         {
    
41.                 if (cnt1 == cnt2)
    
42.                 {
    
43.                         pArr1[j1++] = pArr3[i];
    
44.                         pArr2[j2++] = pArr3[i + 1];
    
45.                         cnt1 += pArr3[i];
    
46.                         cnt2 += pArr3[i + 1];
    
47.                 }
    
48.                 else if (((cnt1 > cnt2) && (pArr3[i] > pArr3[i + 1]))
    
49.                                 || ((cnt1 < cnt2) && (pArr3[i] < pArr3[i + 1])))
    
50.                 {
    
51.                                 pArr1[j1++] = pArr3[i + 1];
    
52.                                 pArr2[j2++] = pArr3[i];
    
53.                                 cnt1 += pArr3[i + 1];
    
54.                                 cnt2 += pArr3[i];
    
55.                 }
    
56.                 else
    
57.                 {
    
58.                         pArr1[j1++] = pArr3[i];
    
59.                         pArr2[j2++] = pArr3[i + 1];
    
60.                         cnt1 += pArr3[i];
    
61.                         cnt2 += pArr3[i + 1];
    
62.                 }
    
63.         }
    
64.        
    
65.         cout<<"The least gap is "<<abs(cnt1 - cnt2)<<endl;
    
66. 
    
67.         delete []pArr3;
    
68. }
    
69. 
    
70. int main()
    
71. {
    
72.     srand((unsigned)time(NULL));        // seed for generating the array
    
73.        
    
74.         int *pArr1 = new int[N];
    
75.         int *pArr2 = new int[N];
    
76. 
    
77.         for (int i = 0; i < N; i++)
    
78.         {
    
79.                 pArr1[i] = rand() & 0xff;
    
80.         }
    
81.        
    
82.         for (int i = 0; i < N; i++)
    
83.         {
    
84.                 pArr2[i] = rand() & 0xff;
    
85.         }
    
86. 
    
87.         cout<<"The initial array: "<<endl;
    
88. 
    
89.         cout<<"Array1:"<<endl;
    
90.         for(int i = 0; i < N; i++)
    
91.                 cout<<pArr1[i]<<" ";
    
92.         cout<<endl;
    
93.        
    
94.         cout<<"Array2:"<<endl;
    
95.         for(int i = 0; i < N; i++)
    
96.                 cout<<pArr2[i]<<" ";
    
97.         cout<<endl;
    
98. 
    
99.         findTheLeastGap(pArr1, pArr2);
    
100. 
     
101.         cout<<"After adjustment: "<<endl;
     
102. 
     
103.         cout<<"Array1:"<<endl;
     
104.         for(int i = 0; i < N; i++)
     
105.                 cout<<pArr1[i]<<" ";
     
106.         cout<<endl;
     
107. 
     
108.         cout<<"Array2:"<<endl;
     
109.         for(int i = 0; i < N; i++)
     
110.                 cout<<pArr2[i]<<" ";
     
111.         cout<<endl;
     
112. 
     
113.         delete []pArr1;
     
114.         delete []pArr2;
     
115.        
     
116. 
     
117.         system("pause");
     
118.     return 0;
     
119. }
     

复制代码

Huawei1900

回复 89# hawk2012


   正解！