【EMC笔试题】N个整数中找出三个数，使其和的绝对值最小

转自：http://blog.csdn.net/BusyCai/article/details/6155929

 

题目描述：给定包含N个数的无序数组S（可能包含负数，0，正数）。求三个数A,B,C，使其和的绝对值最小。

例如：S={-9，0，1，3，6}，A=-9,B=3,C=6,MIN=0

算法解析：

解法一：枚举3个数，O(N*N*N)

解法二：对S排序后枚举其中2个数，二分查找另一个数。O(N*N*LOGN)

解法三：对S排序后枚举其中1个数X，使用双向指针i,j从数组两端更新（注意剔除X）。根据S[I]+S[J]+X的正负号来更新I或J。若为负则I++，否则J--。一旦和为0即退出。同时根据每次得到的和来更新best。最后best即为所求。利用三个变量X,Y,Z记录，可得到任一最优解。复杂度O(N*lOGN+N*N)=O(N*N）

 

期待更好解法 ：）

例如S={-9,0,1,3,6,10}

X=-9

0 1 3 6 10

i           j

X+S[i]+S[j]=-9+0+10=1 > 0 j--

0 1 3 6 10

i        j

X+S[i]+S[j]=-9+0+6=-3 < 0 i++

0 1 3 6 10

    i      j

X+S[i]+S[j]=-9+1+6=-2 < 0 i++

0 1 3 6 10

     i   j

X+S[i]+S[j]=-9+3+6=0 = 0 quit

MIN=0,X=-9,Y=3,Z=6;

-----------------------------------------------------------------------------

算法二没看懂啊

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
using std::sort;

int main()
{
    int a[100], b[100];
    int X,Y,Z;
    int i, j, k;
    int best;
    srand((unsigned)time(NULL));
    int KASE = rand()%10;
    for(int kase = 1; kase <= KASE; kase++){
    printf("/nCase #%d :/n", kase);
    int n = rand()%20;
    if(n <= 2) { printf("Sorry, n is less than 3. /n"); continue; }
    for(i = 0; i < n; i++){
         a[i] = rand()%100;
        if(rand()%2) a[i] *= -1;
    }
    sort(a,a+n);
    for(i = 0; i < n; i++) printf("%d ", a[i]); printf("/n");
    int STD = 1000000;
    for(i = 0; i < n; i++)
        for(j = i+1; j < n; j++)
            for(k = j+1; k < n; k++)
                if(abs(a[i]+a[j]+a[k]) < STD){
                     X = a[i]; Y = a[j]; Z = a[k];
                    STD = abs(a[i]+a[j]+a[k]);
                }
    printf("STD answer is: MIN=%d, X=%d Y=%d Z=%d/n", STD, X, Y, Z);
     best = 1000000;
    for(i = 0; i < n; i++){
        int cur = a[i];
        int cnt = 0;
        for(j = 0; j < n; j++){
            if(j != i) b[cnt++] = a[j];
        }
        int head = 0, tail = n-2;
        while(head < tail){
            int now = cur + b[head] + b[tail];
            if(now == 0 || abs(now) < best){
                 best = abs(now);
                 X = cur;
                 Y = b[head];
                 Z = b[tail];
                if(now == 0) break;
            }
            if(now < 0) head++;
            else tail--;
        }
        if(best == 0) break;
    }
    printf("My answer is: MIN=%d, X=%d Y=%d Z=%d/n", best, X, Y, Z);
    }
    system("pause");
}