`
jigloo
  • 浏览: 6237 次
  • 性别: Icon_minigender_1
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

[Python]华为面试题,交换两个数组的元素使之总和的差值最小。

阅读更多
这是个NPC问题,所以就用穷举发了,在这里给出了一个用python的itertools的解法,个人认为比较简洁。
import itertools

def 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])))
分享到:
评论
28 楼 leero 2011-04-04  
看不懂python,
27 楼 jigloo 2011-04-02  
你确认"解决"了吗?楼上的这些"多项式算法"要不是错误的,要不就是不满足题意。就是我提醒你的"两个数组长度要一致"
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
25 楼 fatdolphin 2011-04-01  
ls的想的太简单了,举个简单的例子,90,1,2,3,4,5,你这个算法就不会返回正确的结果
24 楼 shinkadoki 2011-04-01  
合并,排序。从两端开始取值,各去一半,数组内的值总和相差最小。
23 楼 northc 2011-03-31  
opal 写道
简单易懂的解决方案(java)

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....
22 楼 opal 2011-03-30  
简单易懂的解决方案(java)

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);
	}
}
21 楼 feisuzhu 2011-03-27  
#!/usr/bin/python

# Simulated annealing

from random import randint, random
from math import exp

l1 = [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 *= cool


print "Before:"
print l1
print l2
print abs(sum(l1) - sum(l2))

sa()

print "After:"
l1.sort()
l2.sort()
print l1
print l2
print 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

效果不错
20 楼 神之小丑 2011-03-25  
flysunmicro 写道
合并,排序


按照合并 排序后我写了个。因为排序算法很多,所以就没写。归并排序应该就可以
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:
1	2	3	4	5	11	12	13	14	15	100	100	101	170	
数组array1:
170	100	5	4	3	2	1	和为:285
数组array2:
101	100	15	14	13	12	11	和为:266
19 楼 Excalibur 2011-03-25  
<div class="quote_title">chinpom 写道</div>
<div class="quote_div">
<p><img src="/images/smiles/icon_biggrin.gif" alt=""> 在网上找了一篇帖子,给LZ参考一下:</p>
<pre name="code" class="c">/*

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

*/

/*
    求解思路:

    当前数组a和数组b的和之差为
    A = sum(a) - sum(b)

    a的第i个元素和b的第j个元素交换后,a和b的和之差为
    A' = sum(a) - a[i] + b[j] - (sum(b) - b[j] + a[i])
           = sum(a) - sum(b) - 2 (a[i] - b[j])
           = A - 2 (a[i] - b[j])
    设x = a[i] - b[j]

    |A| - |A'| = |A| - |A-2x|

    假设A &gt; 0,

    当x 在 (0,A)之间时,做这样的交换才能使得交换后的a和b的和之差变小,x越接近A/2效果越好,

    如果找不到在(0,A)之间的x,则当前的a和b就是答案。

    所以算法大概如下:

    在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j,交换相应的i和j元素,重新计算A后,重复前面的步骤直至找不到(0,A)之间的x为止。

*/

把算法大概实现了一下,程序如下:
  1 int test(float a[], float b[], int n)
  2 {
  3     float sumA, sumB; //sumA为数组a总和,sumB为数组b总和
  4     float sum_diff, num_diff; //sum_diff为a,b总和差, num_diff为a,b中各选的两个数之差
  5     float temp1, temp2;    //temp1为 每轮sum_diff/2, temp2为每轮所选两个数之差于temp1最接近的那个
  6     int i, j;
  7     float temp; //用于对调a,b间数
  8     int tempi, tempj;    //每轮所选两个数之差于temp1最接近的那组数
  9     unsigned int flag_sum = 0, flag_num = 0;  //flag_sum为1, sumA大于sumB; flag_num为1, 此轮存在两个数之差小于sum_diff
10
11
12        
13
14     while(1){
15
16         //算出a,b数组和
17         sumA = 0;
18         sumB = 0;
19         for(i=0;i &lt; n;i++)
20         {
21             sumA += a[i];
22             sumB += b[i];
23         }
24
25         if(sumA &gt;= sumB){
26             sum_diff = sumA - sumB;
27             flag_sum = 1;
28         }
29         else
30             sum_diff = sumB - sumA;   
31    
32         temp1 = sum_diff/2;
33         temp2 = temp1;
34         tempi = 0;
35         tempj = 0;   
36    
37         //找出a,b间差值最接近sum_diff/2的那一对数
38         if(flag_sum == 1){    //sumA &gt; sumB
39             for(i=0; i &lt; n; i++)
40                 for(j=0; j &lt; n; j++)
41                
42                     if(a[i] &gt; b[j]){
43                         num_diff = a[i] - b[j];
44                         if(num_diff &lt; sum_diff){
45                             flag_num =1;
46                             if(num_diff &gt;= temp1){
47                                 if(num_diff-temp1 &lt; temp2){
48                                     temp2 = num_diff-temp1;
49                                     tempi = i;
50                                     tempj = j;
51                                 }
52                             }
53                             else{
54                                 if(temp1 - num_diff &lt; temp2){
55                                     temp2 = temp1 - num_diff;
56                                     tempi = i;
57                                     tempj = j;
58                                 }
59                             }
60                         }
61                     }
62         }
63         else{
64             for(i=0; i &lt; n; i++)
65                 for(j=0; j &lt; n; j++)
66                
67                     if(a[i] &lt; b[j]){
68                         num_diff = b[j] - a[i];
69                         if(num_diff &lt; sum_diff){
70                             flag_num =1;
71                             if(num_diff &gt;= temp1){
72                                 if(num_diff-temp1 &lt; temp2){
73                                     temp2 = num_diff-temp1;
74                                     tempi = i;
75                                     tempj = j;
76                                 }
77                             }
78                             else{
79                                 if(temp1 - num_diff &lt; temp2){
80                                     temp2 = temp1 - num_diff;
81                                     tempi = i;
82                                     tempj = j;
83                                 }
84                             }
85                         }
86                     }
87         }
88
89         if(flag_num == 0)
90             break;
91
92         temp = a[tempi];
93         a[tempi] = b[tempj];
94         b[tempj] = temp;
95    
96         flag_num = 0;
97         flag_sum = 0;
98     }
99        
100     for(i=0; i &lt; n;i++)
101         printf("%f\t",a[i]);
102
103     printf("\n");
104
105     for(i=0; i &lt; n;i++)
106         printf("%f\t",b[i]);
107
108     printf("\n");   
109    
110     return 0;
111 }
112
113
114 int main(int argc, char *argv[])
115 {
116
117     float a[3] = {4,5,12};
118     float b[3] = {1,2,3};
119
120     test(a, b, 3);
121
122     return 0;
123 }</pre>
 </div>
<p>输入为:</p>
<p>        int[] arr1 = { 1, 2, 3, 4, 5, 6, 7, 239, 100};<br>        int[] arr2 = { 21, 22, 23, 24, 25, 26, 27, 100, 102 };        </p>
<p>时出现死循环了吧</p>
<p> </p>
<p>至少存在一个答案如下:</p>
<p>int[] arr1 = {  21, 22, 23, 24, 25, 26, 27, 100,100};<br> int[] arr2 = { 1, 2, 3, 4, 5, 6, 7, 239, 102 };</p>
<p> </p>
<p>这种贪心算法能证明可行吗?</p>
<p>我觉得无法证明</p>
<p> </p>
<p> </p>
18 楼 jigloo 2011-03-25  
wjm251 写道
jigloo 写道
这是个NPC问题,所以就用穷举发了,在这里给出了一个用python的itertools的解法,个人认为比较简洁。



这个NPC有点滥用了吧,你知道他的含义吗

不是很清楚,期待你写个n*n*n或者n*n算法出来,注意:"数组里面的元素个数是相等的。"
17 楼 wjm251 2011-03-25  
jigloo 写道
这是个NPC问题,所以就用穷举发了,在这里给出了一个用python的itertools的解法,个人认为比较简洁。



这个NPC有点滥用了吧,你知道他的含义吗
16 楼 chinpom 2011-03-24  
<p><img src="/images/smiles/icon_biggrin.gif" alt=""> 在网上找了一篇帖子,给LZ参考一下:</p>
<pre name="code" class="c">/*

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

*/

/*
    求解思路:

    当前数组a和数组b的和之差为
    A = sum(a) - sum(b)

    a的第i个元素和b的第j个元素交换后,a和b的和之差为
    A' = sum(a) - a[i] + b[j] - (sum(b) - b[j] + a[i])
           = sum(a) - sum(b) - 2 (a[i] - b[j])
           = A - 2 (a[i] - b[j])
    设x = a[i] - b[j]

    |A| - |A'| = |A| - |A-2x|

    假设A &gt; 0,

    当x 在 (0,A)之间时,做这样的交换才能使得交换后的a和b的和之差变小,x越接近A/2效果越好,

    如果找不到在(0,A)之间的x,则当前的a和b就是答案。

    所以算法大概如下:

    在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j,交换相应的i和j元素,重新计算A后,重复前面的步骤直至找不到(0,A)之间的x为止。

*/

把算法大概实现了一下,程序如下:
  1 int test(float a[], float b[], int n)
  2 {
  3     float sumA, sumB; //sumA为数组a总和,sumB为数组b总和
  4     float sum_diff, num_diff; //sum_diff为a,b总和差, num_diff为a,b中各选的两个数之差
  5     float temp1, temp2;    //temp1为 每轮sum_diff/2, temp2为每轮所选两个数之差于temp1最接近的那个
  6     int i, j;
  7     float temp; //用于对调a,b间数
  8     int tempi, tempj;    //每轮所选两个数之差于temp1最接近的那组数
  9     unsigned int flag_sum = 0, flag_num = 0;  //flag_sum为1, sumA大于sumB; flag_num为1, 此轮存在两个数之差小于sum_diff
10
11
12        
13
14     while(1){
15
16         //算出a,b数组和
17         sumA = 0;
18         sumB = 0;
19         for(i=0;i &lt; n;i++)
20         {
21             sumA += a[i];
22             sumB += b[i];
23         }
24
25         if(sumA &gt;= sumB){
26             sum_diff = sumA - sumB;
27             flag_sum = 1;
28         }
29         else
30             sum_diff = sumB - sumA;   
31    
32         temp1 = sum_diff/2;
33         temp2 = temp1;
34         tempi = 0;
35         tempj = 0;   
36    
37         //找出a,b间差值最接近sum_diff/2的那一对数
38         if(flag_sum == 1){    //sumA &gt; sumB
39             for(i=0; i &lt; n; i++)
40                 for(j=0; j &lt; n; j++)
41                
42                     if(a[i] &gt; b[j]){
43                         num_diff = a[i] - b[j];
44                         if(num_diff &lt; sum_diff){
45                             flag_num =1;
46                             if(num_diff &gt;= temp1){
47                                 if(num_diff-temp1 &lt; temp2){
48                                     temp2 = num_diff-temp1;
49                                     tempi = i;
50                                     tempj = j;
51                                 }
52                             }
53                             else{
54                                 if(temp1 - num_diff &lt; temp2){
55                                     temp2 = temp1 - num_diff;
56                                     tempi = i;
57                                     tempj = j;
58                                 }
59                             }
60                         }
61                     }
62         }
63         else{
64             for(i=0; i &lt; n; i++)
65                 for(j=0; j &lt; n; j++)
66                
67                     if(a[i] &lt; b[j]){
68                         num_diff = b[j] - a[i];
69                         if(num_diff &lt; sum_diff){
70                             flag_num =1;
71                             if(num_diff &gt;= temp1){
72                                 if(num_diff-temp1 &lt; temp2){
73                                     temp2 = num_diff-temp1;
74                                     tempi = i;
75                                     tempj = j;
76                                 }
77                             }
78                             else{
79                                 if(temp1 - num_diff &lt; temp2){
80                                     temp2 = temp1 - num_diff;
81                                     tempi = i;
82                                     tempj = j;
83                                 }
84                             }
85                         }
86                     }
87         }
88
89         if(flag_num == 0)
90             break;
91
92         temp = a[tempi];
93         a[tempi] = b[tempj];
94         b[tempj] = temp;
95    
96         flag_num = 0;
97         flag_sum = 0;
98     }
99        
100     for(i=0; i &lt; n;i++)
101         printf("%f\t",a[i]);
102
103     printf("\n");
104
105     for(i=0; i &lt; n;i++)
106         printf("%f\t",b[i]);
107
108     printf("\n");   
109    
110     return 0;
111 }
112
113
114 int main(int argc, char *argv[])
115 {
116
117     float a[3] = {4,5,12};
118     float b[3] = {1,2,3};
119
120     test(a, b, 3);
121
122     return 0;
123 }</pre>
 
15 楼 liuningbo 2011-03-24  
Excalibur 写道
liuningbo 写道
Excalibur 写道
我觉得你这个应该是n^3,当然如果优化一下求和过程,可以降得到n^2。
你能证明这个算法的正确性吗?

经过哥们提醒,改良了下,对于数组长度为m,n有m*n种交换数组,求其中差值最小的,结果应该是正确的


int[] arr1 = { 1, 2, 3, 4, 5, 100, 101 };
int[] arr2 = { 11, 12, 13, 14, 15,100, 170 };

结果为

[100, 1, 2, 3, 4, 100, 101]
311
[5, 11, 12, 13, 14, 15, 170]
240

至少
[1, 2, 3, 4, 5, 100, 170]
285
[11, 12, 13, 14, 15, 100, 101]
266
比代码求出来的效果好

还真是那么回事,兄弟知道哪里缺陷么?这样想到的解决办法就是合并排序再。。。
14 楼 Excalibur 2011-03-24  
liuningbo 写道
Excalibur 写道
我觉得你这个应该是n^3,当然如果优化一下求和过程,可以降得到n^2。
你能证明这个算法的正确性吗?

经过哥们提醒,改良了下,对于数组长度为m,n有m*n种交换数组,求其中差值最小的,结果应该是正确的


int[] arr1 = { 1, 2, 3, 4, 5, 100, 101 };
int[] arr2 = { 11, 12, 13, 14, 15,100, 170 };

结果为

[100, 1, 2, 3, 4, 100, 101]
311
[5, 11, 12, 13, 14, 15, 170]
240

至少
[1, 2, 3, 4, 5, 100, 170]
285
[11, 12, 13, 14, 15, 100, 101]
266
比代码求出来的效果好
13 楼 liuningbo 2011-03-24  
Excalibur 写道
我觉得你这个应该是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种交换数组,求其中差值最小的,结果应该是正确的
12 楼 Excalibur 2011-03-24  
liuningbo 写道
看看写了个 ,实现不需数组长度一致,复杂度O(n^2),求好的算法
   
   /**  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。
你能证明这个算法的正确性吗?
11 楼 Excalibur 2011-03-24  
liuningbo 写道

是一对一交换,不过数组不一定等长吧,


对对,脑子坏了,呵呵
10 楼 liuningbo 2011-03-24  
Excalibur 写道
ggzwtj 写道
楼主有用过背包算法,就是传说中的小偷想偷东西,但是包包的容量是有限的,拿那些东西才能取得最多的东西。

其实可以换个角度想问题,就可以把楼主的问题转换成背包问题了:
如果想让两个数组的和之差最小,这不就是让两个数组的和都非常接近总和的一半!当然很多情况下是不能是得两个数组的和相等,都等于总和的一半。

如果不想等的话,必然有一个数组的和是小于总和一半的。我们要做的就是怎么让这个小的部分最接近总和的一半。

所以,这个问题应该可以转化成0-1背包问题,而这个包的大小就是所有数总和的一半,最后我们要求的是用一定量的数字怎么把这个包装得最满。

所以,这不是一个NP问题。

ps:如果我对楼主的描述没有理解错的话。:)

这个公式我想不出来,尤其是要考虑包内个数必须为数组的长度 交换的意思应该是两个数组长度一致,1对1交换吧

是一对一交换,不过数组不一定等长吧,
9 楼 Excalibur 2011-03-24  
ggzwtj 写道
楼主有用过背包算法,就是传说中的小偷想偷东西,但是包包的容量是有限的,拿那些东西才能取得最多的东西。

其实可以换个角度想问题,就可以把楼主的问题转换成背包问题了:
如果想让两个数组的和之差最小,这不就是让两个数组的和都非常接近总和的一半!当然很多情况下是不能是得两个数组的和相等,都等于总和的一半。

如果不想等的话,必然有一个数组的和是小于总和一半的。我们要做的就是怎么让这个小的部分最接近总和的一半。

所以,这个问题应该可以转化成0-1背包问题,而这个包的大小就是所有数总和的一半,最后我们要求的是用一定量的数字怎么把这个包装得最满。

所以,这不是一个NP问题。

ps:如果我对楼主的描述没有理解错的话。:)

这个公式我想不出来,尤其是要考虑包内个数必须为数组的长度 交换的意思应该是两个数组长度一致,1对1交换吧

相关推荐

    华为-华为od题库练习题之整型数组合并.zip

    【描述】:“华为_华为od题库练习题之整型数组合并”描述了这个压缩文件的内容,即一系列的题目,这些题目集中于如何合并两个或多个整型数组。在编程领域,数组合并是一个常见的问题,尤其是在处理数据结构和算法时...

    经典华为面试题,大家不要错过哦

    【华为面试题】是本文的核心话题,这通常指的是华为公司在招聘过程中可能会问到的问题,涵盖了硬件和软件领域,反映了华为对求职者技能和知识的全面要求。这些面试题旨在评估候选人在技术理解、问题解决、逻辑思维...

    软通动力外派华为面试题

    综合上述分析,软通动力外派华为面试题涵盖了IT行业的多个核心领域,包括数据类型理解、字符串处理、数据库设计以及面试技巧准备。对于希望进入或已在IT行业工作的专业人士来说,深入理解和掌握这些知识点是提升自身...

    Python后端面试题手册集锦关于Python的面试题23页BAT大厂互联网面试题.pdf

    Python后端面试题关于Python的面试题23页BAT大厂互联网面试题.pdf,Python语言特性,操作系统相关,数据库相关,计算机网络相关,编程题。阿里,腾讯,百度,华为,网易,字节,头条,阿里云,腾讯云,京东,饿了么...

    基于Python的华为OD算法面试题-Huawei-OD-Python-master

    基于Python的华为OD算法面试题——Huawei-OD-Python-master。 本项目主要基于Python语言,使用很多Python语言的标准库,希望大家能通过题目,更好地熟悉Python语法,并灵活运用语法特性。 在推荐资料部分,给出了...

    华为od社招python开发面试题.docx

    ### 华为OD社招Python开发面试准备及流程解析 #### 一、华为OD模式简介 华为OD(Outsourcing Developer)模式是一种特殊的招聘方式,指的是通过与第三方人力资源外包公司合作,将员工招聘进来,但实际上这些员工的...

    华为od社招python开发面试题.pdf

    ### 华为OD社招Python开发面试准备及流程解析 #### 一、华为OD模式简介 华为OD(Outsourcing Developer)模式是一种特殊的招聘方式,指的是通过与第三方人力资源外包公司合作,将员工招聘进来,但实际上这些员工的...

    python 华为 od 机试题试题答案.docx

    ### Python华为OD机试知识点详解 #### 一、Python数据类型及特点 Python是一种广泛使用的高级编程语言,因其简洁易读的语法而受到程序员的喜爱。在编写Python程序时,掌握不同数据类型的特性和用途至关重要。 - *...

    面试前的华为Python机考题.zip

    python面试题、知识点,用于程序员应聘学习参考,提供代码+题型等资料 python面试题、知识点,用于程序员应聘学习参考,提供代码+题型等资料 python面试题、知识点,用于程序员应聘学习参考,提供代码+题型等资料 ...

    华为面试经验 华为面试试题

    华为的面试通常包括电话面试、在线测试、技术面试、HR面试和部门经理面试等多个环节。电话面试主要确认基础信息和初步沟通;在线测试多为逻辑分析和编程能力的测试;技术面试则针对具体职位深入考察技术能力;HR面试...

    【免费题库】华为OD机试 - 数组组成的最小数字(Java & JS & Python & C & C++).html

    【免费题库】华为OD机试 - 数组组成的最小数字(Java & JS & Python & C & C++).html

    华为面试试题,各种方面都有

    华为作为全球领先的电信解决方案供应商,其面试涵盖了技术、管理、项目经验、团队合作等多个方面。以下是一些可能出现在华为面试中的核心知识点: 1. **通信技术**:由于华为在通信行业的领导地位,面试中可能会...

    python 华为 od 机试题试题答案.zip

    这个资料对于正在准备华为Python编程相关考试或面试的学员来说具有很高的参考价值。现在,我们将深入探讨其中可能涵盖的Python知识点。 1. **Python基础语法**:这是所有Python学习者必须掌握的部分,包括变量声明...

    华为面试题吐血整理.rar

    这份“华为面试题吐血整理”涵盖了校招面试、软件面试、硬件面试、算法挑战、机考实践以及群面策略等多个方面,旨在全方位提升应聘者的技能和应变能力。以下是对这些知识点的详细解读: 1. **校招面试题**:针对...

    华为OD机试C卷- 数组二叉树(Java & JS & Python).md-私信看全套OD代码及解析

    ### 华为OD机试C卷- 数组二叉树(Java & JS & Python) #### 颈椎题目概述 本题目主要考察的是利用数组来表示二叉树,并且通过深度优先搜索(DFS)的方式寻找从根节点到最小叶子节点的路径。题目描述中给出了非常...

    华为面试试题.rar

    以下将根据"华为面试试题"这一主题,深入探讨可能涉及的多个IT知识点。 一、网络技术 华为在路由器、交换机等领域有深厚的技术积累,面试中可能会涉及OSI七层模型、TCP/IP协议栈、路由协议(如RIP、OSPF、BGP)、...

    揭秘华为OD机试:如何用Python秒杀面试官的算法题!

    ### 揭秘华为OD机试:如何用Python秒杀面试官的算法题! #### 核心知识点概述 本文旨在帮助即将参加华为OD技术面试的候选人准备面试中的算法题部分。通过对几个经典算法题目的深入剖析,包括“两数之和”、“无...

    python基础教程_(华为内部资料)

    Python拥有庞大的标准库,涵盖了网络、系统、数学、文本处理等多个领域。此外,还有许多优秀的第三方库,如NumPy用于科学计算,Pandas用于数据分析,Matplotlib和Seaborn用于数据可视化。 9. **Python与其他技术的...

    华为出品-Python基础入门教程-可爱的Python 共86页.ppt

    【Python技术前景】 Python是一种广泛应用于各种领域的高级编程语言,具有强大的解释性、交互性和...华为出品的这个Python基础入门教程,无疑为学习者提供了全面、深入的指导,帮助他们更好地理解和掌握Python编程。

    【免费题库】华为OD机试 - 整型数组按个位值排序(Java & JS & Python & C & C++).html

    【免费题库】华为OD机试 - 整型数组按个位值排序(Java & JS & Python & C & C++).html

Global site tag (gtag.js) - Google Analytics