面试题集锦_1

题目描述:求数组两两之差绝对值最小的值,只要求出最小值即可,不要求求出具体是那两个数。

常规思路:

  用最简单的算法,时间复杂度为O(N^2)的算法去实现的代码如下:

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<stdlib.h>
 4 int GetMinAbsSubsq(int B[],int len)
 5 {
 6    int min=abs(B[1]-B[0]);
 7    for(int i=0;i<len;i++)
 8        for(int j=i+1;j<len;j++)
 9            if(min>abs(B[i]-B[j]))
10                min=abs(B[i]-B[j]);
11        return min;
12 }
13 int main()
14 {
15     int a[5]={1,2,-3,3,1};
16     int s=GetMinAbsSubsq(a,5);
17     printf("%d\n",s);
18 }
View Code

  为减少时间复杂度,先对数组进行排序,然后再比较相邻两数组之差的绝对值,相邻两数组之差的绝对值最小的即为题目的解。

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<stdlib.h>
 4 int GetMinAbsSubsq(int B[],int len)
 5 {
 6    int min=abs(B[1]-B[0]);
 7    for(int i=2;i<len;i++)
 8            if(min>abs(B[i]-B[i-1]))
 9                min=abs(B[i]-B[i-1]);
10        return min;
11 }
12 int cmp(const void* a,const void* b)
13 {
14     return *(int *)a-*(int *)b;
15 }
16 int main()
17 {
18     int a[5] = {5, -4, 5, 9, -2};
19     qsort(a,5,sizeof(int),cmp);
20     printf("排序后的值为:\n");
21     for(int i=0;i<5;i++)
22         printf("%d",a[i]);
23     printf("\n");
24     int result=GetMinAbsSubsq(a,5);
25     printf("%d",result);
26 }
View Code
原文地址:https://www.cnblogs.com/wj204/p/3110404.html