在csdn上看得一道题，估计有人做过了，题目是：有两个数列，大小都为n，序列元素为任意整数，无序，编写程序，要求通过交换两序列的元素，使两数列元素和的差最小； 我是用两个相同长度的无序数组来做这个题的，我的思路是通过循环交换两个数组中的元素，同时得到每次交换后两数组元素和的差的值，然后将这些个值一次存入到另一个数组中，等到数组交换完成后，再从这个数组中取出最小值，就是要得到的答案；
但是有点问题是，我不确定我程序里的交换元素的方法是不是正确，总感觉有漏掉的，还有就是新数组的大小定义的对不对，最后一个问题就是怎么通过得到的那个最小差值找到此时的两数组。。。就是这三个问题，希望做过的同学给个思路就行了，如果我的程序有问题请提出来，由于手机没流量了，估计要晚点结贴，谢谢了！

1. /*
   
2. 有两个数列，大小都为n，序列元素为任意整数，无序，编写程序，要求通过交换两序列的元素，使两数列元素和的差最小
   
3. */
   
4. class Demo_7
   
5. {
   
6.         public static void main(String[] args)
   
7.         {
   
8.                 //System.out.println("Hello World!");
   
9.                 int[] arr1={8,9,13,43,2,33,1};
   
10.                 int[] arr2={1,6,5,7,11,12,2};
    
11.                 int[] arr3=getArr3(arr1,arr2);
    
12.                 System.out.println("找到两数组交换元素后的最小差值为："+arr3[getMin(arr3)]);
    
13.         }
    
14.         
    
15.         //两数组通过交换元素，获得第三个数组
    
16.         public static int[] getArr3(int[] arr1,int[] arr2)
    
17.         {
    
18.                 int index=0;//第三个数组的角标
    
19.                 int[] arr3=new int[arr1.length*arr2.length];
    
20.                 for (int x=0;x<arr1.length ;x++ )
    
21.                 {
    
22.                         for (int y=0;y<arr2.length ;y++ )
    
23.                         {
    
24.                                 int temp=arr1[x];
    
25.                                 arr1[x]=arr2[y];
    
26.                                 arr2[y]=temp;
    
27.                                 int num=getNum(arr1,arr2);
    
28.                                 arr3[index]=num;
    
29.                                 index++;
    
30.                         }
    
31.                 }
    
32.                 return arr3;
    
33.         }
    
34.         
    
35.         //获得新数组最小元素角标
    
36.         public static int getMin(int[] arr)
    
37.         {
    
38.                 int min=0;
    
39.                 for (int x=0;x<arr.length ;x++ )
    
40.                 {
    
41.                         if(arr[min]>arr[x])
    
42.                                 min=x;
    
43.                 }
    
44.                 return min;
    
45.         }
    
46.         //计算并返回两数组元素和的差的绝对值
    
47.         public static int getNum(int[] arr1,int[] arr2)
    
48.         {
    
49.                 int sum1=0;
    
50.                 int sum2=0;
    
51.                 for (int x=0;x<arr1.length ;x++ )
    
52.                 {        
    
53.                         sum1+=arr1[x];
    
54.                         sum2+=arr2[x];
    
55.                 }
    
56.                 return Math.abs(sum1-sum2);
    
57.         }
    
58. }
    
59. 
    

复制代码

思路基本上没太大问题，但是这个题目。假设数列为a[n]和b[n]
通过交换两序列的元素，使两数列元素和的差最小是指a[i]只能和b[i]交换么？
如果是这样的话那超级简单的，使两数列元素和的差最小实际上就可以转化为数列c[i]=a[i]-b[i]最小，因为交换以后实际和的差的变化就是两个c[i]的变化。
那么一个for循环求出c[n]然后求个最小值即可。

我刚刚看了一下你的程序，大致上没有什么问题，你的那个数组的交换也没有问题，我明白你的意思是不是依次先用arr1[0]和arr2中的每个元素交换，然后是arr2[1]在依次交换arr2中的元素。交换的同时去求和，这个方式是对的，还有那个新的int数组的长度也不错，因为要交换的次数是 arr1的长度*arr2的长度所以这边你的长度定义是可以的。
至于你说的怎么去取回最小值时候的数组，我可以给你说个比较笨的办法就是利用方法的重载
把你的getArr3（）和getnum方法进行重载
public static void getArr3(int[] arr1,int[] arr2,int min)//多传递一个最小值，返回值为void 因为目前还无法一次返回两个值。

        {

                int index=0;//第三个数组的角标
               
                for (int x=0;x<arr1.length ;x++ )

                {

                        for (int y=0;y<arr2.length ;y++ )

                        {

                                int temp=arr1[x];

                                arr1[x]=arr2[y];

                                arr2[y]=temp;
                                boolean b=false;
                                boolean b=getNum(arr1,arr2,int min);//这边也多传递一个最小值
                                //下边加一个判断
                               if(b){
                                   for(int x=0;x<arr1.length;x++){
                                      System.out.print("arr1[]:"+arr1[x]+"  ");
                                      }
                                   System.out.println();
                                  for(int x=0;x<arr2.length;x++){
                                      System.out.print("arr2[]:"+arr2[x]+"  ");
                                      }
                                    System.out.println();
                                      return ;

                               }

                           
                                                  }

                }

               
        }

getNum 方法改为
public static boolean getNum(int[] arr1,int[] arr2,int min)//多传递一个最小值因为一会要进行判断，返回boolean值是为了调用它的方法更好的判断

        {

                int sum1=0;

                int sum2=0;

                for (int x=0;x<arr1.length ;x++ )

                {        

                        sum1+=arr1[x];

                        sum2+=arr2[x];

                }

            if(Math.abs(sum1-sum2)==min){
                   return true;
           }else{
                   return false;
          }

        }
呵呵这样你在main方法中就可以这样写了
public static void main(String[] args)

        {

                int min=0；
                int[] arr1={8,9,13,43,2,33,1};

                int[] arr2={1,6,5,7,11,12,2};

                int[] arr3=getArr3(arr1,arr2);
                min=arr3[getMin(arr3)]);
                System.out.println("找到两数组交换元素后的最小差值为："+arr3[getMin(arr3)]);
                //注意下边开始输出最小值对应的数组了
                getArr3(arr1,arr2，min);//这样在getArr3的重载方法中就输出了最小值对应的数组了。


        }

呵呵，方法比较笨希望能帮到你，还有写的比较匆忙没有时间去修正和测试，有错的地方还需要你给我说啊！

这个是我写的另外一种算法，相对来说更巧妙一些，楼主可以参考一下。

    1.将两数组合并为一个数组al，并排序；

    2.分别获取两个数组的和；

    3.取得al的最大值，放入和较小的那个数组中；

    4.循环2和3，直到al没有元素，或其中有一个数组被填满；

     5.若al还有数据未填写，则将数组填入没有填满的数组中。

代码：

1. import java.util.*;
   
2. import java.math.*;
   
3. public class Demo
   
4. {
   
5.         public static void main(String[] args)
   
6.         {       int[] arr1={8,9,13,43,2,33,1};
   
7.                 int[] arr2={1,6,5,7,11,12,2};
   
8.                 f(arr1, arr2);
   
9.                 System.out.println("交换后的数组为:");
   
10.                 print(arr1);
    
11.                 print(arr2);
    
12.                 System.out.println("两数组交换元素后的最小差值为:"+Math.abs(getSum(arr1)-getSum(arr2)));
    
13.         }
    
14.         public static void f(int[] arr1, int[] arr2)
    
15.         {       LinkedList<Integer> al = new LinkedList<Integer>();
    
16.                 for (int i=0; i<arr1.length; i++)             // 向al中填入数据
    
17.                 {       al.add(arr1[i]);
    
18.                         al.add(arr2[i]);
    
19.                 }
    
20.                 Arrays.fill(arr1, 0);                                   // 对arr1清零
    
21.                 Arrays.fill(arr2, 0);                                   // 对arr2清零
    
22.                 Collections.sort(al);                                // 对al排序
    
23.                 int n1=arr1.length-1, n2=arr2.length-1;
    
24.                 while (!al.isEmpty() && n1 >= 0 && n2 >= 0)        // 填入数据
    
25.                 {       if (getSum(arr1) > getSum(arr2))                    // 将数据填入较小的数组中
    
26.                                 arr2[n2--] = al.remove(al.size()-1);
    
27.                         else
    
28.                                 arr1[n1--] = al.remove(al.size()-1);
    
29.                 }
    
30.                 if (!al.isEmpty())                                        // 处理数据未填写完的情况
    
31.                 {      while (n1 >= 0)
    
32.                                 arr1[n1--] = al.remove(al.size()-1);
    
33.                         while (n2 >= 0)
    
34.                                 arr2[n2--] = al.remove(al.size()-1);
    
35.                 }
    
36.         }
    
37.        public static int getSum(int[] arr)                // 取得当前arr数组的和
    
38.         {       int sum = 0;
    
39.                 for (int n: arr)
    
40.                         sum += n;
    
41.                 return sum;
    
42.         }
    
43.         public static void print(int[] arr)                // 打印arr数组的元素
    
44.         {       for (int n: arr)
    
45.                         System.out.print(n+" ");
    
46.                 System.out.println();
    
47.         }
    
48. }

复制代码

韦念欣 发表于 2012-6-23 22:32
这个是我写的另外一种算法，相对来说更巧妙一些，楼主可以参考一下。
    1.将两数组合并为一个数组al，并 ...

这个方法不错哦！

看了后面的回复才知道我完全误会了楼主的意思。你的意思是两个数列的和的差的绝对值最小吧。首先抱歉我没有将你的程序拿去运行就回复了你，因为我感觉看你的思路和你题目的要求我算是能够理解这个题目了。
说说我的理解吧，我的理解是比如a[]={1,2,3};b[]={1,2,3}，那么其实a和b交换完以后他们的差的最小值应该是1+2+1-(3+2+3)=-4，也就是a[]={1,2,1} b[]={3,2,3}，那么我当时的考虑就是说如果只是a和b对应位置上能交换的话，那么求出a[i]-b[i]的值是最小就可以了，后面的我没有继续说了，也就是说如果是任意位置上都能交换的话，应该是a数列的最大值和b数列的最小值交换能使得它们的差最小（如果a的最大都没有b的最小大的话就不交换，这个时候就已经是和的差最小了），然后a数列的第二大和b数列的第二小交换（如果a的第二大比b的第二小还要小的话就不交换），那么以这个为循环结束条件做一个循环么。
不过看了楼下韦念欣同学的解答，其实我的做法实际上就是将a和b合并成一个数组，然后排序，前半截给a，后半截给b。。
顺便赞一下韦兄的算法，很巧妙。我又搜了一下网上这个题，好像还有点来头，什么微软华为的面试什么的，不过基本上没看到比韦兄算法更巧妙的。
我就不明白了，一个这么有意思的题目，为什么出题这么的不严谨，加个和的差的绝对值不会让人误会么。。不过楼主好像开始就奔着绝对值去的。。

过奖啦，这道题确实出的不够严谨，说的不清楚。要仔细推敲才行。