面试题参考

题目的参考和解答思路来自http://www.cnblogs.com/nokiaguy/archive/2013/01/29/2881476.html

问题描述：

求一个已经排序的数组（升序），数组中可能有正数，负数或0，求数组中元素的绝对值最小的数，要求不能用顺序的比较方法（复杂度需小于

O（n））。

例如，数组{-20，-13，-4,6,77,200}，绝对值最小是4

问题分析：

根据题意知道，数组是排好序的，既然已经排好序了，哪我按照常识，就应该知道绝对值最小的一定是中间的某个数？所以我认为，知道数组的大小，然后取其中间的数，如果是数组的长度是奇数，那就是中间的数，如果是偶数，那就比较中间的两个数的绝对值即可。

参考了其中一人的回帖，然后自己把它用c语言实现下

代码：

View Code

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #define LIST_INIT_SIZE 100
 4 #define LISTINCREMENT 10
 5 typedef struct{
 6 int *elem;
 7 int length;
 8 int listsize;
 9 }Sqlist;
10 void InitList_Sq(Sqlist &L){
11     L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
12     if(!L.elem)
13         printf("存储分配失败！");
14         //exit(0);
15     L.length=0;
16     L.listsize=LIST_INIT_SIZE;//初始存储容量
17 }
18 void ListInsert_Sq(Sqlist &L,int c)
19 {
20     int *p,*q;
21     if(L.length>=L.listsize){
22         p=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
23         if(!p)
24             printf("空间分配失败");
25         L.elem=p;
26         L.listsize+=LISTINCREMENT;
27     }
28     q=&(L.elem[L.length]);//插入的位置,对指针的用法要熟悉p[i]相当于*(p+i)
29     *q=c;
30     ++L.length;
31 }
32 /*int length(int a[])
33 {
34     int i=0;
35     while(a[i]){
36         i++;
37     }
38     return i;
39 }这样计算数组的长度会出现问题，数组越界，也可以给一结束符，
40 所以你现在应该清楚为什么有些题会让你有个结束符，而那时你总是不在意，现在应该意识到这个问题了*/
41 //找绝对值最小，前提要分析清楚，是排序好的，然后分析就容易多了
42 int MinAbs(int *a,int length)//这里的形参不能用数组，要用指针了.
43 {
44 
45     if(a==NULL||length==0)
46      printf("数组a不能为空，且长度要大于0");
47     if(a[0]>=0) return a[0];//全正数
48     if(a[length-1]<=0) return -a[length-1];//全负数
49     if(length==2) return -a[0]>a[1]?a[1]:a[0];//这种情况也可归于下面的分析情况。
50     
51     int index=length/2;
52     while(true)
53     {
54         if(a[index]>0)
55         {
56             if(a[index-1]<=0)
57                 return -a[index-1]>a[index]?a[index]:a[index-1];
58             else
59                 index--;
60         }
61         else if(a[index]<0)
62         {
63             if(a[index+1]>=0)
64                 return -a[index]>a[index+1]?a[index+1]:a[index];
65             else
66                 index++;
67         }
68         else
69             return 0;
70     }
71 }
72 int main()
73 {
74     Sqlist q;
75     InitList_Sq(q);
76     printf("请输入要测试的序列:\n");
77     int i=0;
78     while(true)//暂时以10为结束
79     {
80         scanf("%d",&i);
81         if(i==10)
82             break;
83        ListInsert_Sq(q,i);
84       
85     }
86     int i_len=q.length;
87     printf("你输入序列的长度为：%d\n",i_len);
88     int i_s;
89     i_s=MinAbs(q.elem,i_len);
90     printf("绝对值最小的是：\n");
91     printf("%d\n",i_s);
92 }

总结：
刚开始自己写的求数组的长度的代码，出现问题，数组的访问越界了，现在想来，以前自己有些代码也是这样写的，看来以前测试通过可能也是凑巧啦，对数组的定义与使用要加深理解，如定义数组的时候为它赋值，这时系统就会根据它的赋值，为它分配了固定空间大小，你要计算长度的时候就不能采取遍历的方法，当数组为空时返回其长度，这是个严重的错误。意识到这个问题后，采取了链表的方法，对链表运用加深了理解。