如何交換兩個等長整形數(shù)組使其數(shù)組和的差最小（C和java實現(xiàn)）

1. 問題描述：

　　有兩個數(shù)組a,b，大小都為n,數(shù)組元素的值任意整形數(shù)，無序；
　　要求：通過交換a,b中的元素，使[數(shù)組a元素的和]與[數(shù)組b元素的和]之間的差最小。

2. 求解思路：

當(dāng)前數(shù)組a和數(shù)組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])
   設(shè)x = a[i] - b[j]，則 |A'| = |A-2x|
   假設(shè)A > 0,
   當(dāng)x在(0,A)之間時，做這樣的交換才能使得交換后的a和b的和之差變小，x越接近A/2效果越好, 如果找不到在(0,A)之間的x，則當(dāng)前的a和b就是答案。
所以算法大概如下：
   在a和b中尋找使得x在(0,A)之間并且最接近A/2的i和j，交換相應(yīng)的i和j元素，重新計算A后，重復(fù)前面的步驟直至找不到(0,A)之間的x為止。

3. C語言實現(xiàn)

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <time.h>
  4 #define N 100
  5 int A[N];
  6 int B[N];
  7 //隨機初始化一個數(shù)組
  8 void init(int a[], int n)
  9 {
 10   int i;
 11   for(i = 0; i < n; ++i)
 12     a[i] = rand() % N;
 13 }
 14 //輸出數(shù)組
 15 void print(int a[], int n)
 16 {
 17   int i;
 18   for(i = 0; i < n; ++i)
 19     printf("%d ", a[i]);
 20   printf("\n--------------------------------------------\n");
 21 }
 22  
 23 //求數(shù)組和
 24 int sum(int a[], int n)
 25 {
 26   int i, sum = 0;
 27   for(i = 0; i < n; ++i)
 28     sum += a[i]; 
 29   return sum;
 30 }
 31 //交換整數(shù)
 32 void swap(int *a, int *b)
 33 {
 34   int temp = *a;
 35   *a = *b;
 36   *b = temp;
 37 }
 38 //n1,n2為數(shù)組A和B中實際初始化的元素個數(shù)
 39 int solve(int n1, int n2)
 40 {
 41   int i, j; //循環(huán)迭代變量
 42   int x, y; //用于保存可交換數(shù)字對的索引
 43   int maxSum, minSum; //分別用于保存兩個數(shù)組的數(shù)字之和
 44   int diff; //diff = sum1 - sum2
 45   int maxdiff; // 2 * (A[x] - B[y])
 46   int flag; //標(biāo)記是否找到可交換的數(shù)字對
 47   int temp;
 48   int *pMax; //指向數(shù)字總和較大的數(shù)組
 49   int *pMin; //指向數(shù)字總和較小的數(shù)組
 50         
 51   //隨機初始化數(shù)組
 52   init(A, n1);
 53   init(B, n2);
 54   print(A, n1);
 55   print(B, n2);
 56   //求數(shù)組中數(shù)字之和
 57   maxSum = sum(A, n1);
 58   minSum = sum(B, n2);
 59         
 60   if(maxSum == minSum)
 61     {
 62       printf("There is no need to swap!\n");
 63       return 0;
 64     }
 65         
 66   //令pMax和pMin分別指向數(shù)字總和大的數(shù)組以及總和小的數(shù)組
 67   pMax = A;
 68   pMin = B;
 69   if(maxSum < minSum)
 70     {
 71       pMax = B;
 72       pMin = A;
 73       swap(&maxSum, &minSum);
 74     }
 75   //循環(huán)交換兩個數(shù)組中的數(shù)字對，在交換的過程中，始終
 76   //保持pMax數(shù)組的數(shù)字總和大于或者等于pMin數(shù)組的數(shù)字總和。
 77   //也就是保持diff >= 0
 78   diff = maxSum - minSum;
 79   while(1)
 80     {
 81       flag = 0;
 82       x = y = 0;
 83       maxdiff = 0;
 84       //尋找能夠使diff減小的數(shù)字對。
 85       //從趨勢上來看，
 86       //減小的幅度越大diff收斂的越快,
 87       //while循環(huán)的次數(shù)也越少
 88       for(i = 0; i < n1; ++i)
 89     {
 90       for(j = 0; j < n2; ++j)
 91         {
 92           temp = pMax[i] - pMin[j];
 93           if(temp > 0 && (diff - 2 * temp) >= 0)
 94         {
 95           if(maxdiff < 2 *temp)
 96             {
 97               maxdiff = 2 * temp;
 98               x = i;
 99               y = j;
100               flag = 1;
101             }
102         }
103         }
104     }
105       if(flag) //找到了可以使diff減小的數(shù)字對
106     {
107       printf("swap, pMax[%d]:%d, pMin[%d]:%d\n", x, pMax[x], y, pMin[y]);
108       diff -= maxdiff;
109       swap(pMax + x, pMin + y);
110       print(A, n1);
111       print(B, n2);
112       printf("diff = %d\n", diff);
113 
114     }
115       else //沒有找到可以交換的數(shù)字對,終止while循環(huán)
116     {
117       break;
118     }
119     }
120   return diff; //返回兩個數(shù)組經(jīng)交換后的最小差值
121 }
122 
123 int main(int argc, char **argv)
124 {
125   
126   srand(time(NULL));
127   printf("min difference:%d\n", solve(5, 5)); 
128   //  system("pause");
129   //  pause();
130   return 0;
131 }

4. java實現(xiàn)

  1 import java.util.Arrays;
  2 
  3 /**
  4  * 
  5  * @author Administrator
  6  * 
  7  */
  8 public class TestUtil {
  9     private int[] arrysMin = null;
 10 
 11     private int[] arrysMax = null;
 12 
 13     private int matchNum = 0;
 14 
 15     private boolean hasMatched = false;
 16 
 17     /**
 18      * 返回數(shù)組的所有元素的總和
 19      * 
 20      * @param arrays
 21      *            待計算數(shù)組
 22      * @return 所有元素的總和值
 23      */
 24     public int getArraySum(int[] arrays) {
 25         int sum = 0;
 26         if (null != arrays) {
 27             for (int i : arrays) {
 28                 sum += i;
 29             }
 30         }
 31         return sum;
 32     }
 33 
 34     /**
 35      * 返回數(shù)組的差值
 36      * 
 37      * @param array1
 38      *            集合一
 39      * @param array2
 40      *            集合二
 41      * @return 差值
 42      */
 43     public int getTowArraysMacth(int[] array1, int[] array2) {
 44         Integer l1 = getArraySum(array1);
 45         Integer l2 = getArraySum(array2);
 46 
 47         if ((l1 - l2) / 2 > 0) {
 48             arrysMax = array1;
 49             arrysMin = array2;
 50             return (l1 - l2) / 2;
 51         } else {
 52             arrysMax = array2;
 53             arrysMin = array1;
 54             return (l2 - l1) / 2;
 55         }
 56     }
 57 
 58     private boolean isReturn(int[] arrayMax, int[] arrayMin) {
 59         Integer l1 = getArraySum(arrayMax);
 60         Integer l2 = getArraySum(arrayMin);
 61 
 62         if ((l1 - l2) > 0) {
 63             return false;
 64         } else {
 65             return true;
 66         }
 67     }
 68 
 69     public void doMatch() {
 70         // 保證大的數(shù)組總和永遠是大的，以防遞歸進入死循環(huán)
 71         if (isReturn(arrysMax, arrysMin)) {
 72             return;
 73         }
 74         // 獲取元素總和大的與小的差值平均值
 75         int diff = getTowArraysMacth(arrysMax, arrysMin);
 76         // 使用一個大數(shù)字初始化最小絕對值，后面做比較
 77         int abs = getArraySum(arrysMax);
 78         int tempElement = 0;
 79         // 最終大數(shù)組要交換的下標(biāo)
 80         int maxIndex = -1;
 81         int minIndex = -1;
 82         if (null != arrysMax && null != arrysMin) {
 83             for (int i = 0; i < arrysMax.length; i++) {
 84                 for (int j = 0; j < arrysMin.length; j++) {
 85                     int temp = arrysMax[i] - arrysMin[j];
 86                     if (temp > 0 && diff > temp) {
 87                         // 如果元素差值和元素總和大的與小的差值平均值正好相等，直接交換元素OK
 88                         if (Math.abs(diff - temp) == 0) {
 89                             tempElement = arrysMin[j];
 90                             arrysMin[j] = arrysMax[i];
 91                             arrysMax[i] = tempElement;
 92                             matchNum++;
 93                             hasMatched = true;
 94                             return;
 95                         } else {
 96                             // 否則完全遍歷，最終找出元素差值和總和差值平均值差距最小的兩元素，
 97                             if (abs > Math.abs(diff - temp)) {
 98                                 abs = Math.abs(diff - temp);
 99                                 maxIndex = i;
100                                 minIndex = j;
101                             }
102                         }
103                     }
104                 }
105             }
106             //如果沒有找到匹配項，且在已變換的數(shù)組中找到了滿足條件的變量，則繼續(xù)遞歸
107             if (!hasMatched && (maxIndex != -1 || minIndex != -1)) {
108                 // 交換差距最小的兩元素
109                 System.out.printf("第%d次交換， Max[%d]:%d, Min[%d]:%d\n", ++matchNum, maxIndex, arrysMax[maxIndex], minIndex, arrysMin[minIndex]);
110                 tempElement = arrysMin[minIndex];
111                 arrysMin[minIndex] = arrysMax[maxIndex];
112                 arrysMax[maxIndex] = tempElement;
113                 System.out.println("交換后Max數(shù)組:" + Arrays.toString(arrysMax));
114                 System.out.println("交換后Min數(shù)組:" + Arrays.toString(arrysMin));
115                 System.out.println();
116                 // 遞歸
117                 doMatch();
118             }
119         }
120     }
121 
122     public int getMatchNum() {
123         return matchNum;
124     }
125 
126     /**
127      * @param args
128      */
129     public static void main(String[] args) {
130         TestUtil tu = new TestUtil();
131         int[] a1 = { 11, 2, 4, 6, 47 };
132         int[] a2 = { 4, 5, 8, 9, 2 };
133         System.out.println("交換前數(shù)組a1：" + Arrays.toString(a1));
134         System.out.println("交換前數(shù)組a2：" + Arrays.toString(a2));
135         // 進行第一次分出，兩元素的總和誰大誰小
136         tu.getTowArraysMacth(a1, a2);
137         // 開始進行處理交換
138         tu.doMatch();
139         // 打印交換結(jié)果
140         System.out.println("交換次數(shù)：" + tu.getMatchNum());
141         System.out.println("a1數(shù)組元素和:" + tu.getArraySum(a1));
142         System.out.println("a2數(shù)組元素和:" + tu.getArraySum(a2));
143         System.out.println("交換后原數(shù)組a1:" + Arrays.toString(a1));
144         System.out.println("交換后原數(shù)組a2:" + Arrays.toString(a2));
145     }
146 }

參考鏈接：http://blog.csdn.net/kittyjie/article/details/4386742

　　　　　 http://www.myexception.cn/program/758365.html　（此頁面中的java實現(xiàn)是有問題的，本文已對其作出修改）

posted @ 2014-04-25 16:44 beanmoon 閱讀(2450) 評論(0) 收藏舉報

刷新頁面返回頂部

Beanmoon

如何交換兩個等長整形數(shù)組使其數(shù)組和的差最小（C和java實現(xiàn)）

公告