Chinaunix

标题: 那个8分钟的华为面试题 [打印本页]

---

作者: runforu    时间: 2008-07-16 15:51
标题: 那个8分钟的华为面试题
这些天华为那个使两个数组差最小的题，让我很郁闷，自己钻了牛角尖，总想找个快速有效的算法，最终发现没有。看了一下别人的代码发现这个问题直接置换就行，其实自己也想过这个算法但是没有仔细想，总感觉应该有更有效的算法，自己还要修炼啊，做到论语里的“耳顺”啊。
下面是我把网友的代码整理后修改得到的，比较简洁，而且style也好了不少。希望大家写代码能超过我的code style，哈哈。

#include <cmath>

void EqualizeArray( int * A, int * B, int count )
{
    int sum_A = 0;
    for ( int m = 0; m < count; m++ )
        sum_A += A[m];  
   
    int sum_B = 0;
    for ( int n = 0; n < count; n++)
        sum_B += B[n];     

    int diff_AB = sum_A - sum_B;

    for ( int i = 0; diff_AB && i < count; i++ )
    {
        for ( int j = 0; diff_AB && j < count; j++ )
        {
            int diff = A - B[j];
            if (  abs( diff_AB - 2 * diff ) < abs( diff_AB ) )
            {   
                int tmp = A;
                A = B[j];
                B[j] = tmp;
                diff_AB -= 2 * diff;
            }
        }
    }
}

int main( int argc, char *argv[] )
{
    int A[3] = { 9, 8, 7 };
    int B[3] = { 5, 4, 3 };

    EqualizeArray( A, B, 3 );

    return 0;
}

---

作者: kingsu    时间: 2008-07-16 16:13
不知道事先对数组排序再交换如何。。。

---

作者: gaochang2008    时间: 2008-07-16 16:15
LZ 是很无聊，，

---

作者: silverzi    时间: 2008-07-16 16:17
楼上才无聊

---

作者: silverzi    时间: 2008-07-16 16:18

原帖由 runforu 于 2008-7-16 15:51 发表
这些天华为那个使两个数组差最小的题，让我很郁闷，自己钻了牛角尖，总想找个快速有效的算法，最终发现没有。看了一下别人的代码发现这个问题直接置换就行，其实自己也想过这个算法但是没有仔细想，总感觉应该有 ...

算法描述和证明在哪里？

---

作者: kingsu    时间: 2008-07-16 16:19

原帖由 silverzi 于 2008-7-16 16:17 发表
楼上才无聊utu:" />

---

作者: silverzi    时间: 2008-07-16 16:28
CSDN上有一个动态规划的解法，说是用反证法可证，但没有具体证明过程，现在正在研究。

---

作者: caseboy01    时间: 2012-06-04 22:06

runforu 发表于 2008-07-16 15:51
这些天华为那个使两个数组差最小的题，让我很郁闷，自己钻了牛角尖，总想找个快速有效的算法，最终发现没有 ...

楼主的答案很好，我看代码看懂了。通过代码我看到你的解题方法。

最后一个问题是判断答案的正确性：
做一个嵌套for循环，for(int i = 0; i < n; i++) { for (int j=0; j < n; j++　) {　．．．　}} 不存在一个a b[j]使得 | sum(a) - sum(b) | 更小。

现在问题是EqualizeArray迭代完成了以后，怎么能保证上面这个判断成立（因为没有执行最后这一个循环判断）。

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2