免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: forrestgang

华为面试题(8分钟写出代码) [复制链接]

论坛徽章:
1
寅虎
日期:2014-11-30 21:25:54
发表于 2014-06-03 08:55 |显示全部楼层
优化了下算法:

遍历A B数组所有两个数字之间的差,找到可以让A B的和差变得最小的那对数,交换,然后重复遍历,直到找不到为止。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>

  4. #define MOD     100000
  5. #define N       10000
  6. int A[N];
  7. int B[N];

  8. void swap(int *x, int *y)
  9. {
  10.         int t;
  11.         t = *x; *x = *y; *y = t;
  12. }

  13. int array_sum(int *first)
  14. {
  15.         int *p, sum = 0;
  16.         for(p = first; p < first + N; p++)
  17.                 sum += *p;
  18.         return sum;
  19. }

  20. void array_print(int *first)
  21. {
  22.         int *p;
  23.         for(p = first; p < first + N; p++)
  24.                 printf("%d ", *p);
  25.         printf("\n");
  26. }

  27. int main()
  28. {
  29.         int sum_a, sum_b, delta;
  30.         int i, j, a, b;
  31.         int tmp;
  32.         srand(time(NULL));
  33.         for(i = 0; i < N; i++)
  34.         {
  35.                 A[i] = rand() % MOD;
  36.                 B[i] = rand() % MOD;
  37.         }

  38.         while(1)
  39.         {
  40.                 sum_a = array_sum(&A[0]);
  41.                 sum_b = array_sum(&B[0]);
  42.                 delta = sum_a - sum_b;
  43.         //      array_print(&A[0]);
  44.         //      array_print(&B[0]);
  45.                 printf("sum(A)=%d sum(B)=%d sum(A)-sum(B)=%d\n", sum_a, sum_b, delta);

  46.                 if(delta == 0)
  47.                         break;

  48.                 a = b = N;
  49.                 tmp = delta;
  50.                 for(i = 0; i < N; i++)
  51.                         for(j = 0; j < N; j++)
  52.                                 if(abs(delta - 2 * (A[i] - B[j])) < abs(tmp))
  53.                                 {
  54.                                         tmp = delta - 2 * (A[i] - B[j]);
  55.                                         a = i;
  56.                                         b = j;
  57.                                 }
  58.                 if(a == N)
  59.                         break;

  60.                 swap(&A[a],  &B[b]);
  61.         }
  62.         return 0;
  63. }
复制代码

论坛徽章:
1
寅虎
日期:2014-11-30 21:25:54
发表于 2014-06-03 10:50 |显示全部楼层
本帖最后由 vbs100 于 2014-06-03 10:53 编辑

回复 285# cjaizss
花了一个多小时 ,把所有回复都重新看了一遍,只有这个是效率最高的,也就是我上面实现的代码。其它多数的都是找到可以把和差变小的就交换,这样虽然是正确的但收敛的速率就比找到最小的就低很多。这个贴子应该可以结贴了

   

论坛徽章:
1
寅虎
日期:2014-11-30 21:25:54
发表于 2014-06-03 10:51 |显示全部楼层
本帖最后由 vbs100 于 2014-06-03 10:52 编辑

发重了。。。

论坛徽章:
0
发表于 2014-06-05 15:54 |显示全部楼层
全部加起来    然后找出组合数组和最接近总和的一半即可!

论坛徽章:
0
发表于 2014-06-11 15:01 |显示全部楼层
唉,8分钟早过了~

论坛徽章:
0
发表于 2014-07-13 17:51 |显示全部楼层
我有个想法,不过还没去代码实现哈,

第一遍扫描
    从头到尾,按顺序比较对位的元素。
    记录到前一个下标时两个数组的差值,比较当前下标的两个元素,若利于减小差值,则交换 A[i]<-->B[i];否则,继续扫描下一个下标。直到尾部。
    记录差值最大的下标和差值。

第二遍扫描
    由于可能在两个数组尾部发生差值的剧烈变化,所以可能需要扫描第二遍。主要就是比较造成较大差值的值,比较第一遍扫描记录的较大差值下标和差值,若这两个差值比较接近且差值方向相反,则交换之。

理想情况下,应该可以完成楼主的问题。

欢迎讨论哈。。。

论坛徽章:
0
发表于 2014-07-23 19:19 |显示全部楼层
回复 2# zhhui2000

2n个数一起排,比较好吧。


   

论坛徽章:
11
2015年迎新春徽章
日期:2015-03-04 09:55:282017金鸡报晓
日期:2017-02-08 10:39:4215-16赛季CBA联赛之辽宁
日期:2016-12-15 10:24:1715-16赛季CBA联赛之佛山
日期:2016-11-30 09:04:2015-16赛季CBA联赛之江苏
日期:2016-04-29 15:56:1215-16赛季CBA联赛之同曦
日期:2016-04-12 13:21:182016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之山东
日期:2016-02-16 11:37:52每日论坛发贴之星
日期:2016-02-07 06:20:00程序设计版块每日发帖之星
日期:2016-02-07 06:20:0015-16赛季CBA联赛之新疆
日期:2018-01-09 16:25:37
发表于 2014-07-25 13:23 |显示全部楼层
这个问题完全可以转化为这个问题

从M个数里面找出N个,让他们的和尽量接近 P
M=2N
P=sum(M2n)/2N

用动态规划来解

class nlist:
    """从M个数里面找出N个,让他们的和尽量接近 P
    """
    def __init__(self):
        self.nums_m = [] # M个数的数组
        self.value_n= 0  # N的值
        self.value_p= 0  # P的值
        self.nums_n = [] #被选定的N个数
        self.sum_n  = 0  #N个数的和的快照
        self.nums_l = [] #剩下的M-N个数
        return
    #
    def main(self,mlist,N,P):
        """计算入口
        从M个数里面找出N个,让他们的和尽量接近 P
         1. 对M个数排序,从小到大
         2. 取前N个作为和 的初始值
         3. 考虑替换 其中一个数,导致和增加最小的,此时交换两个数
         4. 重复子问题 当 和<P
        """
        self.nums_m[:] = mlist
        self.value_n,self.value_p = N,P
        self.nums_m.sort()
        self.nums_n[:] = self.nums_m[:N]
        self.nums_l[:] = self.nums_m[N:]
        self.sum_n = sum(self.nums_n)
        while self.sum_n < P:
            a,b = self.find_min()
            if a is None:
                break
            #预测交换a,b后,后的和是否更接近P
            d1 = P-self.sum_n
            d2 = d1 - (b-a)
            if d2 < 0 and d1<=-d2:
                break
            self.change(a,b)
            continue
        return self.nums_n,self.sum_n
    #
    def find_min(self):
        """
        从self.NumN中找出a,self.NumL中找出b
        使得交换a,b后导致self.sum是增加的,并且增加的量是最小
        """
        a,b = None,None
        for i in self.nums_n:
            for j in self.nums_l:
                if i < j and (not a or j-i<b-a):
                    a,b = i,j
        return a,b
    def change(self,a,b):
        self.sum_n += b-a
        self.nums_n.remove(a)
        self.nums_n.append(b)
        self.nums_l.remove(b)
        self.nums_l.append(a)
        return

for n in range(100+1):
    nlist().main([1,1,2,3,5,10,20,30,30,50,50,100,],5,n)

论坛徽章:
0
发表于 2014-07-26 22:56 |显示全部楼层
回复 432# vbs100
先别急着结啊,麻烦把您上面的代码解释下吧,delta - 2 * (A - B[j]); 这个主要是干什么呢,谢谢

   

论坛徽章:
0
发表于 2014-07-30 14:14 |显示全部楼层
本帖最后由 ywj1225 于 2014-07-30 14:32 编辑
  1. #!/usr/bin/python
  2. # -*- coding: utf-8 -*-

  3. # 有两个数组a,b,大小都为n,数组元素的值任意,无序;
  4. # 要求:通过交换a,b中的元素,使数组a元素的和与数组b元素的和之间的差最小


  5. a = [1, 2, 3, 4, 5, 50]
  6. b = [9, 8 ,7, 6, 100, 25 ]

  7. c = a + b

  8. c.sort()
  9. c.reverse()

  10. a = []
  11. b = []
  12. a.append(c[0])
  13. b.append(c[1])

  14. lenth = len(c)
  15. i = 2

  16. while i < lenth:
  17.     if sum(a) > sum(b):
  18.         if i+1 < lenth and sum(a) > sum(b) + c[i] + c[i+1]:
  19.             b.append(c[i])
  20.             a.append(c[lenth-1])
  21.             i += 1
  22.             lenth -= 1
  23.             b.append(c[i])
  24.             a.append(c[lenth-1])
  25.             i += 1
  26.             lenth -= 1
  27.         elif sum(a) > sum(b):
  28.             b.append(c[i])
  29.             i += 1
  30.             a.append(c[i])
  31.             i += 1
  32.         else:
  33.             a.append(c[i])
  34.             i += 1
  35.             b.append(c[i])
  36.             i += 1
  37.     else:
  38.         if i+1 < lenth and sum(b) > sum(a) + c[i] + c[i+1]:
  39.             a.append(c[i])
  40.             b.append(c[lenth-1])
  41.             i += 1
  42.             lenth -= 1
  43.             a.append(c[i])
  44.             b.append(c[lenth-1])
  45.             i += 1
  46.             lenth -= 1
  47.         elif sum(a) > sum(b):
  48.             a.append(c[i])
  49.             i += 1
  50.             b.append(c[i])
  51.             i += 1
  52.         else:
  53.             b.append(c[i])
  54.             i += 1
  55.             a.append(c[i])
  56.             i += 1

  57.             
  58. print a
  59. print b
  60.         
  61. print sum(a)-sum(b)
复制代码
总体由大到小排序放入c中,最大的两个数分别放两个数组a和b里,如果a的和比b的和加上c里面剩余数字最大的两个还大的话,把c里面最大的两个数放入b中,最小的两个数放入a中;如果a的和单单比b的和大的话,把c中两个最大的数中大的放入b中,小的放入a中。。。
只是进行一些测试,不知道完全行得通不,还望指点。

发现问题很大了。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP