华为面试题(8分钟写出代码)

ubanwin

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

既然说明了是可以交换a,b中的元素，而且a,b元素都是n，那么只要再申明一个临时数组c，其中存放a,b中的元素，对其进行排序，然后将c中相邻元素相减（diff+=c[i+1]-c[i];i+=2;//这里是从小到大排序），最后得到的diff就是最小差之和了。

举例说明  如果a中含1，3，5  b中含2，4，6   在这样的情况下貌似2楼的方法可行，但是如果换成a:1,2,3   b:4,5,6   这样就不行，而把a,b中的元素放到同一个数组里面就不会出现这种情况。

楼上所提让我类似的想到快速排序法的数轴。。。

qzn928

感觉应该先取最大的，然后再依次决定谁取剩下的数，差最后的结果，肯定是大的数决定的 回复 13# ccjjhua


   

A.com

太阁4的酒馆里有个赌博项目和这个道理差不多。排序挨个取数肯定不能得到正确结果。解题的正确思路应该是先求两个数组的总和，然后除2得出理想值。然后就是根据数组本身的总和来求修正值，通过交换数据来缩小修正值到最小就可以了。

feihuadao

难道不是动态规划？


   

bigtree3721

其实这就是天平问题或者背包问题：

１：首先把A和B数组按降序排序，用快速排序就可以（ｑｓｏｒｔ）．

２：把这两个数组用归并排序，形成一个２ｎ的降序数组C。

３：按天平问题或者背包问题解决。

　３.１. 　sum(A)=sum(B)=0

  ３.２.　从数组C中取出当前的最大元素，放到数组ａ和ｂ中数组元素之和最小的那个数组中，如果二者相

　　　　　等，则选择

　　并更新该数组之和。

　３.３　重复第２步，直到ａ或者ｂ数组放满。

　３．４　数组C其余的元素放到ａ或者ｂ中未满的那个数组中。

bigtree3721

其实这就是天平问题或者背包问题：

１：首先把A和B数组按降序排序，用快速排序就可以（ｑｓｏｒｔ）．

２：把这两个数组用归并排序，形成一个２ｎ的降序数组C。

３：按天平问题或者背包问题解决。

　３.１. 　sum(A)=sum(B)=0

  ３.２.　从数组C中取出当前的最大元素，放到数组ａ和ｂ中数组元素之和最小的那个数组中，如果二者相

　　　　　等，则选择数组个数小的那个数组。　　并重新累计该数组之和。

　３.３　重复第２步，直到ａ或者ｂ数组放满。

　３．４　数组C其余的元素放到ａ或者ｂ中未满的那个数组中。

babynew

把两个数组合并后从小到大排序，再依次分配给两个数组？

bigtree3721

>把两个数组合并后从小到大排序，再依次分配给两个数组？
不是，详细看清看我上面的解法。

bigtree3721

input:
a  142 3 2 -12
b  31  4 2 1
ouput:

a  142 2 1 -12
b  31  4 3 2


#include <cstdlib>
#include <iostream>
#include <ctime>
#include <assert.h>

using namespace std;

void swapdata(int& x, int &y){
   int temp;
   temp=x;
   x=y;
   y=temp;
   return;
}

void Display(int data[],int begin,int end){
if(data==NULL) return;
for(int index=begin;index<=end;index++){
  cout<<data[index]<<" ";
}
cout<<endl;
}
//data1 and data2 are sorted descend

bool select(int total[],int array1[],int array2[],int len){
assert(total !=NULL &&array1 !=NULL && array2 != NULL && len >0 );
int sum1,sum2,index1,index2;
sum1=sum2=index1=index2=0;

while(index1<len && index2<len) {
   if(sum1>sum2) {
       sum2+=*total;
       array2[index2++] = *total++;
     }
   else {
     sum1+=*total;
     array1[index1++] = *total++;
    }      
}

while(index1<len)
   array1[index1++] = *total++;

while(index2<len)
   array2[index2++] = *total++;

return true;   
}
int* mergesort(int data1[],int data2[],int length1,int length2) {
  assert(data1 != NULL && data2 != NULL);   
  assert(length1 >=0 && length2 >=0 );  

  int index=0,len1=0,len2=0;
  int *data3=new int[length1+length2];
  
   
  while( len1<length1 && len2<length2 ){
    data3[index++]= data1[len1]>data2[len2]? data1[len1++]:data2[len2++];
  }

   while(len1<length1)  
    data3[index++]=data1[len1++];
  
  while(len2<length2)  
       data3[index++]=data2[len2++];
   
  cout<<"merge sorted ->"<<endl;
  Display(data3,0,length1+length2-1);
   
   return data3;   
}
/*
*
*/
bool myqsort2(int data[],int begin,int end){
   bool result=true;
   
  if( data==NULL || end < 0 || begin < 0 || begin > end)
      return false;   
   if(begin==end)
       return result;
   
    int compare_point,i,j,pilotkey;
   
    srand((unsigned int)time(NULL));
    compare_point=begin + rand()%(end-begin+1);
    pilotkey=data[compare_point];
   
    swapdata(data[compare_point],data[end]);
   
    i=begin;
    j=end;
   
    while(i<j) {   
        while(data[i] >= pilotkey && i<j)
         i++;     
        if(i<j)
          swapdata(data[i],data[j--]);   
     
         while(data[j] <= pilotkey && i<j)
             j--;        
         if(i<j)         
           swapdata(data[i++],data[j]);     
     }
   
    myqsort2(data,begin,i-1);
    myqsort2(data,i+1,end);

}

//descending sort
bool myqsort(int* data,int begin,int end){
  bool result=true;
   int compare_point,midvalue,pivot,index;
   int tempdata;
   
  if( data==NULL || end < 0 || begin < 0 || begin > end)
      return false;
   
   if(begin==end)
       return result;
  
   //generate a random number between begin and end
    srand((unsigned int)time(NULL));
    compare_point=begin + rand()%(end-begin+1);
   
   midvalue=data[compare_point]; //use the middle point
  
  //exchange pivot value into the last element of array
  swapdata(data[compare_point],data[end]);
   
  index=begin;
  pivot=begin-1;
  while(index <= end){
    if(data[index] > midvalue){   
       if((++pivot) != index){  
        swapdata(data[pivot],data[index]);   
       }      
      }
    index++;   
  }
  
//exchange pivot value into the last element of array   
  swapdata(data[++pivot],data[end]);
   
  myqsort(data,begin,pivot-1);
  myqsort(data,pivot+1,end);
  
  return result;
}

int main(int argc, char** argv) {
   int data1[]={142,3,2,-12};
   int data2[]={31,4,2,1};
   int *data3=NULL;

   cout<<endl<<"before selection, data list -> "<<endl;
   Display(data1,0,sizeof(data1)/sizeof(int)-1);
   Display(data2,0,sizeof(data2)/sizeof(int)-1);
   
   myqsort(data1,0,sizeof(data1)/sizeof(int)-1);
   myqsort(data2,0,sizeof(data2)/sizeof(int)-1);
   
   data3=mergesort(data1,data2,4,4);
//  cout<<endl<<"after merge sorting"<<endl;
//  Display(data3,0,7);
   
   select(data3,data1,data2,4);
   
   cout<<endl<<"after selection,data list -> "<<endl;
   Display(data1,0,sizeof(data1)/sizeof(int)-1);
   Display(data2,0,sizeof(data2)/sizeof(int)-1);
   delete []data3;
   return 0;
}

zmy235

这么难的题！
感觉要用动态规划哦。