黑马程序员技术交流社区

标题: 华为面试题,关于数组的.题和代码都在 [打印本页]

作者: 灵魂灬丿丶轩 时间: 2016-3-28 17:13
标题: 华为面试题,关于数组的.题和代码都在
/*    两个数值a,b元素数都为n,使a,b数组重新组合,
   使a数组各元素的和与b数组各元素的和只差最小.

   思路: 先将a,b数组组合成c数组,c数组排序后,a取c数组两头,b取c数组中间.
排序后首位相加最接近,所以差最小
            看不明白的地方可以回复.
   */

class Dome2 {
public static final int MIUI = 520;
public static void main(String[] args) {
int[] arr = {1,5,3,4,2,9};
int[] brr = {6,7,1,9,8,4};
int[] crr =new int[12];
for (int i = 0;i < crr.length/2 ;i++ ) {
crr[i] = arr[i];
}
for (int i = arr.length;i < crr.length ; i++) {
crr[i] = brr[i-arr.length];
}
for (int i = 0;i < crr.length ;i++ ) { //冒泡排序法
for (int j = 0;j < crr.length-1;j++ ) {
if (crr[j]<crr[j+1]) {
int temp = crr[j];
crr[j] = crr[j+1];
crr[j+1] = temp;
}
}
}
for (int i = 0;i < crr.length ;i++ ) { //重组数组,a数组取c数组两头,b取c数组中间
if (i <= 2) {
arr[i] = crr[i];
}else if (i>=3 && i <=8) {
brr[i-3] = crr[i];
}else {
arr[i-6] = crr[i];
}
}
String stra="{";
for (int i = 0;i < arr.length ;i++ ) { //输出a数组
if (i==arr.length-1) {
stra+=arr[i] + "}";
}else {
stra+=arr[i]+", ";
}
}
System.out.println("a数组为:  " + stra + "\n");

String strb="{";
for (int i = 0;i < brr.length ;i++ ) { //输出b数组
if (i==brr.length-1) {
strb+=brr[i] + "}";
}else {
strb+=brr[i]+", ";
}
}
System.out.println("b数组为:  " + strb);
}
}

运行结果.png (40.17 KB, 下载次数: 29)

运行结果

作者: dxw 时间: 2016-3-28 17:14
感谢分享，收藏了

作者: user_lqb 时间: 2016-3-28 17:20
感谢分享！

作者: 马儿不吃草 时间: 2016-3-28 20:32
有思路就很好做了,收藏了

作者: 赵国政 时间: 2016-3-28 21:00
很厉害啊！

作者: 风二中kyf 时间: 2016-3-29 12:11
6666666666666666

作者: a292723685 时间: 2016-3-29 12:31
使a数组各元素的和与b数组各元素的和只差最小
没看懂这句话,能解释清楚吗?

作者: 灵魂灬丿丶轩 时间: 2016-3-29 21:57

a292723685 发表于 2016-3-29 12:31
使a数组各元素的和与b数组各元素的和只差最小
没看懂这句话,能解释清楚吗? ...

都怪我打错别字了

作者: 神勇小汪汪 时间: 2016-3-29 22:31
感谢分享

作者: 赵浩霖 时间: 2016-3-29 22:46
感谢分享，收藏下

作者: toxic罐头儿 时间: 2016-3-29 22:59
学习了学习了

作者: zhangchao5292 时间: 2016-3-29 23:07
技术不错，赞一个

作者: 小凡帅哥 时间: 2016-3-29 23:08
真任性，不愧是0310的好手

作者: 兵蜂 时间: 2016-3-29 23:24
非常改写分享,谢谢

作者: ping3014 时间: 2016-3-29 23:36
举个例子验证一下：也是12个数，如下：
1,2,3,10,20,30,40,50,60,100,200,300
不一定能实现吧？

作者: zhang3216858 时间: 2016-3-29 23:46
感谢分享,谢谢楼主了

作者: ipursue 时间: 2016-3-30 10:05
好题，很考验思维逻辑，数学思想不好的很难想到

作者: ipursue 时间: 2016-3-30 10:07

ping3014 发表于 2016-3-29 23:36
举个例子验证一下：也是12个数，如下：
1,2,3,10,20,30,40,50,60,100,200,300
不一定能实现吧？ ...

可以实现，保证重新分配的两个数组元素和相差最小

作者: zhangchao555 时间: 2016-3-30 10:23
感谢分享

作者: cohle1992 时间: 2016-3-30 11:00
学习了,收藏!

作者: sdx_1234 时间: 2016-3-30 13:21
感谢分享已收藏

作者: onceIme 时间: 2016-3-30 14:58
不一定把，如果是奇数个数的数组呢，而且首尾相加的和有可能是最小，中间两个相加和是最大的情况

作者: 钱伟 时间: 2016-3-30 17:10
6666666666666666

作者: Lee♥晓蕾 时间: 2016-3-30 17:27
确实能提高呀~

作者: 灵魂灬丿丶轩 时间: 2016-3-30 21:08

ping3014 发表于 2016-3-29 23:36
举个例子验证一下：也是12个数，如下：
1,2,3,10,20,30,40,50,60,100,200,300
不一定能实现吧？ ...

可以实现的首先a,b数组都是n,然后c数组元素就是2n,保证了元素个数是偶数.我这个思路来源于高斯的1-100的求和思想, 1+100 = 2+ 99=101,所以这样得到的差才会最小

作者: 灵魂灬丿丶轩 时间: 2016-3-30 21:09

ipursue 发表于 2016-3-30 10:05
好题，很考验思维逻辑，数学思想不好的很难想到

就是想到了高斯的求和原理,才这样做的

作者: 灵魂灬丿丶轩 时间: 2016-3-30 21:11

onceIme 发表于 2016-3-30 14:58
不一定把，如果是奇数个数的数组呢，而且首尾相加的和有可能是最小，中间两个相加和是最大的情况 ...

可以实现的首先a,b数组都是n,然后c数组元素就是2n,保证了c的元素个数是偶数.

作者: xiaofushen 时间: 2016-3-30 22:09
本帖最后由 xiaofushen 于 2016-3-30 22:13 编辑

我觉得隔着一个取比较好,arr数组取crr数组偶数索引的元素,brr数组取crr数组奇数索引的元素,不然当crr数组不是等差数列,并且差异较大时,可能楼主的方法不是最满足题意的:
            for (int i = 0;i < crr.length;i++ ) {
                     if (i % 2 == 0) {                            //arr数组取crr数组偶数索引的元素
                              arr[i / 2] = crr[i ];
                     }else {                                        //brr数组取crr数组奇数索引的元素
                              brr[(i - 1) / 2]= crr[i ];
                     }
               }
当然,就算这样也有可能不能保证差异最小,最保险的方法是在限制条件的情况下遍历所有可能,找出最小差异的两组数组.
如有不对,还请指正.

作者: 灵魂灬丿丶轩 时间: 2016-3-30 22:34

xiaofushen 发表于 2016-3-30 22:09
我觉得隔着一个取比较好,arr数组取crr数组偶数索引的元素,brr数组取crr数组奇数索引的元素,不然当crr数组不 ...

嗯嗯,这个思想也是正确的,不过最优方案,我也不能确定.我也是看到了这个题,自己做了一下,和大家分享一下.

作者: xiaofushen 时间: 2016-3-30 22:49

灵魂灬丿丶轩发表于 2016-3-30 22:34
嗯嗯,这个思想也是正确的,不过最优方案,我也不能确定.我也是看到了这个题,自己做了一下,和大家分享一下. ...

关于最优方案,我再想想,顺便问一下楼主是0310的吗?我也是啊.

作者: 妄想年少轻狂 时间: 2016-3-30 23:13
本帖最后由妄想年少轻狂于 2016-3-30 23:34 编辑

灵魂灬丿丶轩发表于 2016-3-30 21:08
可以实现的首先a,b数组都是n,然后c数组元素就是2n,保证了元素个数是偶数.我这个思路来源于高斯的1-100的 ...

c = ｛1，2，3，10，20，30，40，50，60，100，200，300｝这个数组按照你的算法分成
a = ｛1，2，3，100，200，300｝和是606，b = ｛10，20，30，40，50，60｝和是210，两个数组
差是396
看题目没要求分成两个长度一样的数组，那么差最小的应该是
c = ｛1，2，3，40，60，100，200｝和是406，d = ｛10，20，30，50，300｝和是410，两个数组
差是4
高斯求1-100和是因为1-100是等差数列，而 c 的元素不是一个等差数列
我的思路是求 c 的和，然后除以2得到一个数x，让 a 数组的和尽可能接近x。
初步设想伪代码如下：int index = c.length-1;
max = c[index];       如果 max > x 就让 a = ｛max｝，其余元素组成 b，否则执行下面循环
for(i = index, i >= 0, i--) {          反向遍历数组 c
   if(c[index] < x ) {
      将 c[index] 加入 a 数组
      index-- ；
      x -= c[index]
   }
}
结果就取出了300，100，3，2，1
和是406
其余的数是200，60，50，40，30，20，10
和是410

作者: huangkai521 时间: 2016-3-30 23:17
好题，学习了

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2