腾讯QQ笔试题分享——其一

昨天参加腾讯QQ笔试，其中的一道编程题目觉得挺有意思，在这里特意想和大家分享一下.

题目是这样的：

给定一个整数数组，求出具满足如下条件的数：

1、该数字之前的每一个数均小于该数值。

2、该数字之后的每一个数均大于该数值。

令问：设计一个执行时间最短的算法，并编程实现。（时间复杂度能不能为O(n)?）

这里给出一个自己的解决方法，欢迎各位大牛批评指正。

算法思想如下：

首先根据数据长度申请两个数组，指针名分别为max_arr和min_arr.

其次，扫描给定数组array，同时让max_arr记录每一个位置处的最大值。

再次，反向扫描数组array，并记录当前扫描过的元素中最小的，如果该最小值min和max_arr相应位置索引处的值相同，那么该值就是所求值。

最后，继续执行第三步，直到min的值小于max_arr相应位置索引处的值时停止，算法结束。

上述算法可以在O(n)时间内完成任务，并找出所有符合条件的数值.最坏情况下需要循环2n次，最好情况是循环n次。

下面将源码贴出，以供大家分享。注：下面的算法是优化之后的，能够在最多n次循环中找出全部符合条件的数值。程序只接受正整数的输入，若想接受signed int类型的数据输入，可以适当修改用做记录的数组的初始值来实现。

int mid(int *arr, int len) {
int i = 0, j;
int *max_arr = (int *)calloc(sizeof(int),len);
int *min_arr = (int *)calloc(sizeof(int),len);
int min = 0;
int max = 0;
int flag = 0;
max_arr[0] = arr[0];
min_arr[len-1] = arr[len-1];

for (i=1;i<len;i++) {
if (max_arr[i-1] < arr[i]) {
max_arr[i] = arr[i];
} else max_arr[i] = max_arr[i-1];

if (min_arr[len-i]> arr[len-i-1]) {
min_arr[len-i-1] = arr[len-1-i];
} else min_arr[len-i-1] = min_arr[len-i];

if (max_arr[i] == min_arr[i]) {
printf(" %d", max_arr[i]);
flag =1;
}

if ((i<<1) == len-1) continue;

if (max_arr[len-i-1] == min_arr[len-i-1]) {
printf(" %d", max_arr[len-i-1]);
flag =1;
}
}

if (flag)
printf("\n");
else
printf(" (none)\n");

free(max_arr);
free(min_arr);

return 0;
}


完整的程序可以在这里下载：

文件:	mid-arr.c.tar.gz
大小:	0KB
下载:	下载