[Python]华为面试题，交换两个数组的元素使之总和的差值最小。这是个NPC问题，所以就用穷举发了，在这里给出了
[Python]华为面试题，交换两个数组的元素使之总和的差值最小。
这是个NPC问题，所以就用穷举发了，在这里给出了一个用python的itertools的解法，个人认为比较简洁。
import itertoolsdef funcProduct(a, b): for c in itertools.permutations(b): for d in itertools.product(*[list(itertools.permutations(x)) for x in zip(a, c)]): yield zip(*d)a = [1,2,3,4]b = [5,6,700,800]print min(funcProduct(a,b), key=lambda x:abs(sum(x[0])-sum(x[1])))
/** arr1={1,2,3}; * arr2={22,33,44,55}; * 交换两个矩阵数据 */ public void exchange(){ int index=0; int len=arr1.length; int currMinus=getMinus(); while(true){ for (int i = 0; i < arr2.length; i++) { echangeMatrix(index,i);//交换值 if(currMinus>getMinus()){ currMinus=getMinus();//一次循环中找到最小minus的 }else { echangeMatrix(index,i);//若不是则不交换，即再换同一位置一次 } } index++; if(index>=len){ break; } } } private void echangeMatrix(int index,int des){ int temp=0; temp=arr1[index]; arr1[index]=arr2[des]; arr2[des]=temp; } /**计算和 * ryuuninbou * @return int */ private int getMinus(){ int sum1=0; int sum2=0; for (int i = 0; i < arr1.length; i++) { sum1+=arr1[i]; } for (int i = 0; i < arr2.length; i++) { sum2+=arr2[i]; } return Math.abs(sum1-sum2); }
我觉得你这个应该是n^3，当然如果优化一下求和过程，可以降得到n^2。
你能证明这个算法的正确性吗？
private int primalMinus=0;private int sum1=0; private int sum2=0; private void primalMinus(){ for (int i = 0; i < arr1.length; i++) { sum1+=arr1[i]; } for (int i = 0; i < arr2.length; i++) { sum2+=arr2[i]; } primalMinus=Math.abs(sum1-sum2);} public void exchange(){ primalMinus();//计算最初差值 int index=0; int len=arr1.length; int currMinus=primalMinus; while(true){ for (int i = 0; i < arr2.length; i++) { echangeMatrix(index,i);//交换值 int afterChange=getMinus(); if(currMinus>=afterChange){ currMinus=afterChange;//一次循环中找到最小minus的 }else { echangeMatrix(index,i);//若不是则不交换，即再换同一位置一次 } } index++; if(index>=len){ break; } } } private void echangeMatrix(int index,int des){ int temp=0; temp=arr1[index]; arr1[index]=arr2[des]; sum1+=arr1[index]; sum2-=arr1[index]; arr2[des]=temp; sum1-=arr2[des]; sum2+=arr2[des]; primalMinus=Math.abs(sum1-sum2); } /**计算和 * ryuuninbou * @return int */ private int getMinus(){ return primalMinus; }
经过哥们提醒，改良了下，对于数组长度为m，n有m*n种交换数组，求其中差值最小的，结果应该是正确的<pre name="code" alt="[Python]华为面试题，互换两个数组的元素使之总和的差值最小"> 在网上找了一篇帖子，给LZ参考一下：</p>
<pre name="code" name="code">public void mergeSort(int[] array1,int[] array2){/* * 这里将这两个数组合并排序成一个数组 * 这里就省略 */int[] array=new int[array1.length+array2.length];for(int i=0;i<array1.length;i++){array[i]=array1[i];array[i+array1.length]=array2[i];}System.out.println("合并数组array：");for(int i:array)System.out.print(i+"\t");System.out.println();sumResolve(array,array1,array2);}private void sumResolve(int[] array,int[] array1,int[] array2){array1[0]=array[array.length-1];array2[0]=array[array.length-2];int array1Sum=array1[0];int array2Sum=array2[0];int index1=1;int index2=1;for(int i=array.length-3;i>=0;i--){if(array1Sum>=array2Sum&&index2<array2.length){array2[index2]=array[i];array2Sum+=array2[index2];index2++;}else if(index1<array1.length){array1[index1]=array[i];array1Sum+=array1[index1];index1++;}}System.out.println("数组array1：");for(int j:array1)System.out.print(j+"\t");System.out.print("和为："+array1Sum);System.out.println();System.out.println("数组array2：");for(int j:array2)System.out.print(j+"\t");System.out.print("和为："+array2Sum);System.out.println();}
int[] arr1 = { 1, 2, 3, 4, 5, 11,12 };int[] arr2 = { 13, 14, 15,100,100,101, 170 }; mergeSort(arr1, arr2);outoutPut:合并数组array：123451112131415100100101170数组array1：17010054321和为：285数组array2：1011001514131211和为：266#!/usr/bin/python# Simulated annealingfrom random import randint, randomfrom math import expl1 = [randint(0,1000) for i in xrange(120)]l2 = [randint(0,1000) for i in xrange(120)]l1.sort()l2.sort()def sa(): t = 1000.0 cool = 0.999 sl1 = sum(l1) sl2 = sum(l2) ev = abs(sl1 - sl2) while t>0.00001: a = randint(0,len(l1)-1) b = randint(0,len(l2)-1) nsl1 = sl1 - l1[a] + l2[b] nsl2 = sl2 - l2[b] + l1[a] nev = abs(nsl1 - nsl2) d = nev - ev if d<0 or (d>0 and exp(-d/t)>random()): ev = nev sl1, sl2 = nsl1, nsl2 l1[a], l2[b] = l2[b], l1[a] t *= coolprint "Before:"print l1print l2print abs(sum(l1) - sum(l2))sa()print "After:"l1.sort()l2.sort()print l1print l2print abs(sum(l1) - sum(l2))
Before:
[9, 10, 16, 30, 34, 49, 59, 63, 81, 96, 105, 106, 112, 115, 116, 123, 133, 141, 142, 184, 190, 201, 201, 203, 215, 217, 229, 236, 242, 259, 262, 274, 274, 276, 293, 294, 297, 299, 304, 311, 315, 320, 321, 360, 368, 377, 377, 385, 387, 391, 408, 411, 426, 433, 434, 443, 459, 493, 496, 498, 504, 507, 512, 518, 549, 554, 560, 575, 634, 640, 642, 649, 652, 660, 664, 686, 686, 698, 700, 702, 720, 724, 735, 759, 768, 789, 789, 792, 812, 817, 817, 824, 826, 829, 841, 848, 861, 861, 862, 871, 874, 882, 888, 891, 896, 908, 908, 924, 925, 930, 930, 930, 940, 941, 947, 960, 973, 976, 981, 998]
[4, 4, 31, 37, 46, 48, 84, 98, 105, 110, 117, 119, 120, 122, 122, 145, 157, 172, 183, 187, 190, 193, 204, 215, 226, 231, 233, 233, 248, 250, 269, 291, 292, 333, 333, 341, 365, 377, 378, 380, 387, 394, 404, 406, 412, 412, 413, 414, 418, 418, 420, 420, 424, 432, 433, 438, 441, 450, 455, 460, 475, 477, 487, 491, 531, 545, 555, 561, 574, 585, 606, 620, 624, 641, 646, 652, 654, 658, 661, 668, 668, 675, 679, 684, 704, 709, 709, 711, 715, 724, 727, 734, 754, 760, 767, 775, 783, 787, 797, 803, 816, 819, 831, 833, 837, 865, 875, 891, 893, 895, 913, 913, 937, 948, 958, 964, 965, 968, 979, 1000]
1422
After:
[4, 9, 10, 16, 30, 31, 37, 46, 49, 96, 98, 105, 106, 110, 116, 117, 120, 122, 123, 141, 142, 145, 190, 201, 203, 204, 215, 231, 248, 259, 262, 274, 293, 297, 315, 321, 333, 341, 360, 368, 377, 380, 385, 387, 387, 391, 394, 404, 412, 414, 418, 418, 420, 432, 433, 450, 455, 460, 475, 491, 493, 504, 512, 549, 554, 555, 560, 575, 585, 640, 642, 649, 652, 652, 658, 661, 668, 679, 686, 698, 700, 709, 709, 715, 734, 754, 760, 767, 768, 787, 789, 792, 803, 817, 819, 824, 826, 831, 841, 848, 861, 861, 862, 865, 888, 891, 893, 895, 908, 913, 924, 930, 930, 937, 940, 958, 968, 973, 998, 1000]
[4, 34, 48, 59, 63, 81, 84, 105, 112, 115, 119, 122, 133, 157, 172, 183, 184, 187, 190, 193, 201, 215, 217, 226, 229, 233, 233, 236, 242, 250, 269, 274, 276, 291, 292, 294, 299, 304, 311, 320, 333, 365, 377, 377, 378, 406, 408, 411, 412, 413, 420, 424, 426, 433, 434, 438, 441, 443, 459, 477, 487, 496, 498, 507, 518, 531, 545, 561, 574, 606, 620, 624, 634, 641, 646, 654, 660, 664, 668, 675, 684, 686, 702, 704, 711, 720, 724, 724, 727, 735, 759, 775, 783, 789, 797, 812, 816, 817, 829, 833, 837, 871, 874, 875, 882, 891, 896, 908, 913, 925, 930, 941, 947, 948, 960, 964, 965, 976, 979, 981]
0
效果不错import java.util.*;public class Main {public static void main(String args[]) {Integer a[] = { 1,2,3,4,5,11,12 };Integer b[] = { 13,14,15,100,100,101,170};Integer d,v;List<Integer> c = new ArrayList<Integer>(Arrays.asList(a));c.addAll(Arrays.asList(b));Collections.sort(c,new Comparator<Integer>(){public int compare(Integer a,Integer b) {return b.compareTo(a);}});int i=1,j=1;a[0] = c.get(0);b[0] = c.get(1);d = a[0] - b[0];for (int k=2; k<c.size() ; k++) {v = c.get(k);if (i >= a.length) {b[j++] = v;d -= v;continue;}if (j >= b.length) {a[i++] = v;d += v;continue;}if (d < 0) {a[i++] = v;d += v;} else {b[j++] = v;d -= v;}}System.out.println(Arrays.asList(a).toString());System.out.println(Arrays.asList(b).toString());System.out.println("diff=" + d);}}import java.util.*;public class Main {public static void main(String args[]) {Integer a[] = { 1,2,3,4,5,11,12 };Integer b[] = { 13,14,15,100,100,101,170};Integer d,v;List<Integer> c = new ArrayList<Integer>(Arrays.asList(a));c.addAll(Arrays.asList(b));Collections.sort(c,new Comparator<Integer>(){public int compare(Integer a,Integer b) {return b.compareTo(a);}});int i=1,j=1;a[0] = c.get(0);b[0] = c.get(1);d = a[0] - b[0];for (int k=2; k<c.size() ; k++) {v = c.get(k);if (i >= a.length) {b[j++] = v;d -= v;continue;}if (j >= b.length) {a[i++] = v;d += v;continue;}if (d < 0) {a[i++] = v;d += v;} else {b[j++] = v;d -= v;}}System.out.println(Arrays.asList(a).toString());System.out.println(Arrays.asList(b).toString());System.out.println("diff=" + d);}}
楼上V5.... 24 楼 shinkadoki 2011-04-01 合并，排序。从两端开始取值，各去一半，数组内的值总和相差最小。 25 楼 fatdolphin 2011-04-01 ls的想的太简单了，举个简单的例子，90，1，2，3，4，5，你这个算法就不会返回正确的结果 26 楼 wjm251 2011-04-02 jigloo 写道wjm251 写道jigloo 写道这是个NPC问题，所以就用穷举发了，在这里给出了一个用python的itertools的解法，个人认为比较简洁。
这个NPC有点滥用了吧，你知道他的含义吗
不是很清楚，期待你写个n*n*n或者n*n算法出来，注意:"数组里面的元素个数是相等的。"
可以在多项式时间内解决的判定性问题属于P类问题
可以在多项式时间内验证一个解是否正确的问题称为NP问题。已知P属于NP，目前的困难是P是否等于NP，即NP是否属于P
这类特殊的NP问题就是NP完全问题（NPC问题，C代表complete）。NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！！这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。
以上是从网上某篇文章中抄出来的。总结一下，这个问题被大家以多项式时间解决了，如果是NPC，那么大家就证明了N=NP 27 楼 jigloo 2011-04-02 你确认"解决"了吗？楼上的这些"多项式算法"要不是错误的，要不就是不满足题意。就是我提醒你的"两个数组长度要一致" 28 楼 leero 2011-04-04 看不懂python，
