1. 有一个整数数组，请求出两两之差绝对值最小的值。记住，只要得出最小值即可，不需要求出是哪两个数。（Microsoft）
方法1：两两作差求绝对值，并取最小，O( n2 )。
方法2：排序，相邻两点作差求绝对值，并取最小，O( nlgn ).
方法3：有没有O( n )的解法？（选择网络）
设数组A = { a1, a2, … , an }, 求 s = min( |ai – aj| ), 其中1<= i, j <=n.
设B = { b1, b2, … , bn-1 }, 且 bi = ai – ai+1
即：b1 = a1 – a2, b2 = a2 – a3, b3 = a3 – a4, …
于是有如下规律：
例如：a3 – a5 = ( a3 – a4 ) + ( a4 – a5 ) =b3 + b4
a1 – a6 = b1 + b2 + … + b5
即：ai – aj = bi + … + bj-1
则数组A中任意两个数的差，都可以用数组B中一个字段的和表示。
则原问题可以转换为：
在数组B中，求连续的某一段，使其和的绝对值最小。
例如 B = { 1, -2, 3, -1, -9, 7, -5, 6 }；
则绝对值最小值为0，具体是{ -2, 3, -1 } 或 {3, -1, -9, 7}
解到这边，卡住了。。。
方法4：计数排序，相邻两点作差求绝对值，并取最小。
#include<iostream>using namespace std;int MinErrorSuquence(int* a,int length){int bigest1=0;//记录正数的最大值int bigest2=0;//记录负数的最小值 int Error=65536;//用于比较for(int i=0;i<length;i++)//bigest1为数组中最大的正数，bigest2为最小的负数{ if(a[i]>=0&&a[i]>bigest1) bigest1=a[i]; if(a[i]<0&&a[i]<bigest2) bigest2=a[i];}int timesOfNumber[bigest1-bigest2];//定义每个整数出现的次数，存放在数组里面。。 //例如5出现2次，那么a[5]=2 for(int i=bigest2;i<=bigest1;i++){timesOfNumber[i]=0;}for(int i=0;i<length;i++){int tmp=a[i]; ++timesOfNumber[tmp];}int index=0;for(int i=bigest2;i<=bigest1;i++)//排序{for(int j=0;j<timesOfNumber[i];j++){a[index]=i;++index;}}for(int i=0;i<length-1;i++)//求差的最小值 { if(a[i+1]-a[i]<Error) Error=a[i+1]-a[i];} return Error;}int main(void){int a[9]={-2,-1,-6,5,-12,8,-4,-7,-3};cout<<MinErrorSuquence(a,9)<<endl;for(int i=0;i<9;i++)//重新排列后的数组cout<<a[i]<<endl;
return0;
}
解题后的几点思考：
1：数组下标可以为负整数，，这个平时可能比较少注意到。一般情况下都是从0开始，在这边比较特殊。
2：算法4遍历的3次数组，第一次：取最大最小值。第二次，排序。第三次：相邻两项做差，比较。
复杂度为：O（n）？ 还是O（3n）？
灿烂甜美!那一瞬的激-情绽放,催人奋进!胜利,永远属于为梦想奋斗的人新乐吧
