有兩個數組a,b，大小都為n；通過交換a,b中的元素，使sum(a)-sum(b)最小。，sum-sum

有兩個數組a,b，大小都為n；通過交換a,b中的元素，使sum(a)-sum(b)最小。，sum-sum

今天在浏覽網頁的時候,發現了一個叫做  華為面試題（8分鐘寫出代碼） 的鏈接,不確定真實性,純屬好奇,就點進去看看

這個可能是很老的題目吧,因為我看到這題目時,底下有好多評論了.提到XX排序,內存占用,等等詞匯

小丑是新人,也想用自己的方法解一下題目,如有雷同,純屬巧合

解:

(1) 有前輩在解題時用到排序,但我認為沒有必要,排序後的sum(a) - sum(b), 與任意雜亂順序的sam(a) - sam(b) 結果肯定是一致的 ;

(2) 如果 c[i] = a[i] - b[i]  ,  sum 為 數組c[]的加和  ;a[i]與b[i]交換後 ,c[i] = b[i] - a[i] , sum_new 是 新的數組c[ ]的加和;

(3) sum - sum_new = a[i]-b[i]-(b[i]-a[i]) = 2*(a[i] - b[i]) = 2*c[i],  sum_new = sum - 2*c[i]  ;

CODE:

int sum = 0;

int sum_new = 0;

int i = n;

int c[n] = {0};

while(i--){

    a[i]-b[i] = c[i];

    sum + = c[i];

}

while(n--){

    sum_new = sum - 2 * c[n];    

    if(sum_new * sum_new < sum * sum){    //絕對值變小,說明交換正確

        a[n]^= b[n];       

        b[n] ^= a[n];

        a[n] ^= b[n];     

        }
}