有一个整数数组，请求出两两之差绝对值最小的值
//1、有一个整数数组，请求出两两之差绝对值最小的值
//方法1：两层for循环，求出每两个数之间的差的绝对值，再进行比较.算法时间复杂度:O(n^2)
//注意：若绝对值等于0,那么可以直接退出,因为绝对值等于0就是最小的了
#include &stdio.h&
#include &stdlib.h&
#define N 10
int minAbs(int *num);
void main()
&int num[N] = {1,6,29,11,22,17,50,67,88,59};
&min = minAbs(num);
&printf("%d",min);
int minAbs(int *num)
&int min,n;
&min = abs(num[0] - num[1]);
&for(i = 0;i & N;i++)
&&for(j = i+1;j &
abs(num[i] - num[j]);
&&&if(n ==
//方法2：对整个数组进行排序,需要O（n*logn）的时间。然后遍历一次数组，求相邻两个数之间的
//差的绝对值，若等于0，直接返回.需要O（n）的时间复杂度，总的时间复杂度需要O（n+n*logn）
//排序：用快排
#include &stdio.h&
#include &stdlib.h&
#include &math.h&
#define N 10
int pattion(int num[],int p,int r);
void QuickSort(int num[],int p,int r);
int smallAbs(int *num);
void main()
&int num[N] =
{12,89,16,78,30,135,78,362,275,351};
&QuickSort(num,0,N-1);
&printf("经过快速排序之后数组如下:\n");
&for(i = 0;i & N;i++)
&&printf("]",num[i]);
&printf("\n");
&small = smallAbs(num);
&printf("数组中绝对值之差最小是]",small);
int pattion(int num[],int p,int r)
&int j = r+1;
&int x = num[p];
&&while(num[++i] &
&&while(num[--j] &
&&if(i &= j)
&&temp = num[i];
&&num[i] = num[j];
&&num[j] =
&num[p] = num[j];
void QuickSort(int num[],int p,int r)
&if(p & r)
&&int q = pattion(num,p,r);
&&QuickSort(num,p,q-1);
&&QuickSort(num,q+1,r);
int smallAbs(int *num)
&int small = abs(num[0] - num[1]);
&if(0 == small)
&&return 0;
&for(i = 1;i & N;i++)
&&k = abs(num[i],num[i+1]);
&&&small =
&&&if(0 ==
&&&&return
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。4487人阅读
面试题（7）
一 题目描述：
　　有一个整数数组，请求出两两之差绝对值最小的值，只要求出最小值即可，不要求求出是哪两个数。
　　二 常规思路：
　　求解此题的寻常思路是什么？观察题目我注意到后面强调不要求求出两个数，那么最最简单的O(n^2)的算法显然做了很多无用功。嗯，好，既然这个办法不行想想其他的。对于数组也就是序列之类的题，有一种很常用的思路那就是预处理。这道题目貌似是可以的。
　　首先，对数组进行排序，这个可以在O(n*logn)时间之类解决，然后，有了这个预处理，就会想到，绝对值之差最小值肯定只能发生在预处理的数组之后的相邻的元素上，这个是很显然的事实。那么我们便可以循环一遍数组，记下两两之间绝对值的最小值，那么所求得到值便是解答，总的时间复杂度是O(n*logn)。仔细想想这种方法，很明显，排序减小了我们所需要搜寻的解空间，从而达到了减小时间复杂度的目的。不过这个解法仍然不能让人满意，因为我们还是浪费时间求出了最终的两个元素，而题目不要求，所以，这肯定不是最优解。
　　三 转化的思想
　　再仔细观察题目，我们可以猜到，最优解应该是只求出最小值而不求出具体的元素的，那么该怎么做呢？我们可能能想到用辅助数组，但是却很难想到怎么做这个辅助。其实这道题我一直在思考如何通过常规的思维去想到这个最优解，不过我当时没有想出来，而这才是我写这篇博客的原因，即促使我了解并对这种思路印象深刻，不过这可能只适用于解这题或者类似能让我联想到这种方法的题，这背后更一般的思维（可以叫做转化，但是还可以更具体些）我还没有想到，希望想到的同学联系我！。
　　好了，本题要做的辅助数组是这样一个数组，设它为Bn.原来题目中给定的数组是An,则Bn等于：
　　B1 = A1 - A2;
　　B2 = A2 - A3;
　　B3 = A3 - A4;
　　......
　　Bn-1 = An-1 - An.
　　注意，Bn的长度是n-1，正好比An要小一个。聪明的同学看到这个辅助数组，立马就能猜到原因了，因为这样做的话，我们能够把这道看似无从下手求出最优解的问题转化为求Bn的绝对值最小的最长连续子序列和，因为Bn的连续子序列和便是An任意两数之差（注意，由于题目要求的是绝对值最小，所以求出A1-A2等效于得出A2-A1），例如：
　　A2 - A5 = B2 + B3 + B4 = A2 - A3 + A3 - A4 + A4 - A5 = A2 - A5
　　实际上，任何Ai - Aj（i&j） = sigma(k=i -& k=j-1)(k)
　　这样的话，我们就成功把问题转化为了连续子序列问题，不过和我们以前做的最大或最小连续子序列还不完全相同，此处是绝对值最小。那么怎么样的值可能是绝对值最小呢？正数最小或者负数最大，也就是说在数轴上离0更近的数其绝对值更小，基于此我们可以得到如下的方法。
　　和原来求最大连续子序列和一样，要用数学归纳法思考，我们直接看归纳基础，
　　归纳基础： 假设已知B1..Bk的绝对值最小连续的连续子序列和是Min(Bk)
　　我们利用这个求解B(k+1)，加入B(k+1)后有可能比Min(Bk)小的只可能是以B(k+1)结尾的绝对值最小的连续子序列和，如果把这个和Min(Bk)比较就可以知道是否需要更新Min(Bk)。所以，我们加强这个归纳基础。
　　更强的归纳基础： 假设已知B1..Bk的绝对值最小连续的连续子序列和Min(Bk)，以及以Bk结尾的绝对值最小连续子序列和Suffix(Bk)
　　有了这个归纳，我们可以去想如何维护这个Suffix(Bk),目标是使的Suffix(B(k+1))仍然是以B(k+1)结尾的最小连续子序列和。如果按照求最小和的思路，那便是只要Suffix(Bk)是正数便置它为0，因为如果它是正数，那么在后续求Suffix(B(k+1))时就肯定比用0要更大，因为正数会使得整个值变大，而0不会。同样的道理，我们只要使得求Suffix的时候比直接置0更小即可，否则我们可以直接把Suffix(B(k+1))置0以获得更小值。由于我们求的是绝对值最小，直接按最小值的思路是不行的，因为可能某个Suffix是暂时求得一个很小的负数，下次加上某个正数会使得它成为很小的正数，所以不能以正数负数作定论而要以与0的距离。所以我们应该采取比较符号的方法，如果当前suffix和下一个数的符号相反，那么可以继续相加以求得下一个suffix，因为我们可以获得绝对值更小的suffix；如果是同号，无论正负一定会比把当前suffix置0更糟糕，因为这将使得下次的suffix在数轴上离0更远。所以我们维护Suffix的公式如下：　
　　Suffix(B(k+1)) = Suffix(B(k)) + B(k+1）， if (Suffix(B(k))*B(k+1)) & 0
　　Suffix(B(k+1)) = 0, if (Suffix(B(k))*B(k+1)) ) & 0
　　这样我们一直归纳下去，便可以求得最终的Min(Bn)，即可求得解。整个的时间复杂度是O(n),空间复杂度是O(n)。
　　四 程序
　　程序如下：
1 //TestAlgo.cpp : Defines the entry point for the console application.
5 #include&stdafx.h&
7 #include&iostream&
8 #include&cmath&
9 usingnamespace
11 intGetMinAbsoluteSubsequence(intB[],intnLen)
13 intnGlobal=INT_MAX;
15 intnSuffix=0;
17 for(inti=0; i&nL i++)
19 nSuffix+=B[i];
21 if(abs(nSuffix)&abs(nGlobal))
23 nGlobal=nS
27 if(i+1&nLen)
29 if(nSuffix*B[i+1]&0)
30 nSuffix=0;
34 returnabs(nGlobal);
37 intGetMinAbsoluteDiff(intA[],intnLen)
39 //create aid array
40 int*b=newint[nLen-1];
41 memset(b,0,sizeof(b[0])*(nLen-1));
42 for(inti=0; i&nLen-1; i++)
44 b[i]=A[i]-A[i+1];
47 returnGetMinAbsoluteSubsequence(b,nLen-1);
50 int_tmain(intargc, _TCHAR*argv[])
52 intA[]={1,20,200,16,13};
53 intnLen=5;
55 cout&&GetMinAbsoluteDiff(A,nLen);
57 getchar();
58 return0;
　　五 总结
　　整个思路过程便是这样，总的来说，这类题目还是很有思考价值的，至少让我们体会到了各种美，也能深刻领会转化的意义。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：29845次
排名：千里之外
转载：19篇
评论：10条
(7)(4)(2)(7)2267人阅读
C/C++面试（239）
这个题目其实和那个左边减去右边的差最大那个题目类似，只是这里要多加几个判断，代码如下：
// maxAndmin.cpp : 定义控制台应用程序的入口点。
#include &stdafx.h&
#include &iostream&
#include &cmath&
int getMax(int a[],int len)
int max=a[0];
int maxDiff=0;
int diff=a[0]-a[1];
for (int i=2;i&i++)
if (a[i-1]&max)
max=a[i-1];
diff=max-a[i];
if (diff&maxDiff)
return maxD
int getMin(int a[],int len)
int min=a[0];
int diff=a[0]-a[1];
if(diff&0)
int minDiff=
for (int i=2;i&i++)
if (a[i-1]&abs(min))
min=a[i-1];
diff=min-a[i];
if (diff&0)
if (diff&minDiff)
return minD
int _tmain(int argc, _TCHAR* argv[])
int a[]={-5,-1,11,6,-2};
int len=sizeof(a)/sizeof(int);
cout&&getMin(a,len);
system(&pause&);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：634677次
积分：10389
积分：10389
排名：第1248名
原创：410篇
评论：105条
(32)(14)(1)(17)(7)(2)(10)(59)(22)(57)(49)(76)(24)(19)(22)(1)有一个整数数组,请求出两两之差绝对值最小的值_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
有一个整数数组,请求出两两之差绝对值最小的值
上传于||文档简介
&&提供了一种解决该问题的方法,欢迎测试与点评,希望提供更加清晰的解决思路。
你可能喜欢python编程 输入一组整数数组,求出两两之差的最小绝对值.只需得出最小值 如：输入：[10,3,12,9] 输入：1
错误的齿轮
代码如下:------a = [10,8,2,45,69,38,11,15] #假设该列表为需要输入的一组数a.sort(reverse = True) #首先对这组数进行从大到小的排序print a #输出排序结果min = a[0] #令min变量记录该列表中最大的值for i in range( len(a) -1 ):#i用来控制列表下标,元素个数-1为了防止下面的相减越界if a[i] - a[i+1] < min:#当前一个数减后一个小于当前min里的值时,更新最小值min = a[i] - a[i+1]print min------运行结果:>>> [69,45,38,15,11,10,8,2]1>>>
谢了，兄弟，可似乎与题目要求有点不符
如果输入的是负数，结果就不对了，而且还是负数
自己思考才是王道, 这样的题算是基础且十分容易的了, 我相信你能解决, 如果这个解决不了, 我觉得你还是不要学编程了。
先不要想着用Python怎么实现, 而要想着如果是在数学上如果让我在纸上做这道理我的思路是什么, 思路一清楚再去想着怎么用编程语言实现, 这么说吧, 你能想到的在编程语言上都能描述出来, 谷歌百度翻手册, 总能解决, 就拿你追问的后面那句, "而且还是负数" , 是负数可以把它转成整数不是,
>>> abs(-1)
你看, 这不就变成整数了, 至于如何处理正整数与负整数混合在一起的情况你就自己尝试解决吧, 我只能帮到这里了, 别人直接给出答案的答案是最无意义的。
为您推荐：
其他类似问题
#!/usr/bin/env python# coding=utf-8"""find min diff of two member"""import itertoolsimport sysdef find_min_diff(lst):
min_ = sys.maxint
for x, y in i...
>>> a = [10,3,12,9]>>> a.sort(reverse = True)>>> min(a[i]-a[i+1] for i in range(len(a)-1))1>>> .这样也可以，思路是完全一样的。>>> a = [10,3,12,9]>>> a.sort()>>> a[3, 9, 10, 12]>>> min(a[i+1]-a[i] for i in range(len(a)-1))1>>>
扫描下载二维码}