两道面试题
talia
2.如何用c语言实现一个栈：
要求：1）栈的数据类型有多种，比如int，char或者函数指针等。
2）栈的大小不确定(即能够动态的分配空间)。
先说我对第一题的想法：
很yy的思路是：第一次循环找到最大值，第二次循环找到第二大值（不是最大值而大于其他值）。总时间是2n,
算是O(n)的。
另外一个想法是用基数排序，返回排序后的第二个位置的数值。总时间为O(cn)，c为这些数的最长位数。
第二题。。。
肖海彤
吴彧文
如果是遍历两遍，虽然当然也是O(n)，但是需要比较n-1+n-1-1 = 2n-3次。
这个证明题是算法导论上的一个习题，我以前写了一个解答：
http://blog.csdn.net/atyuwen/archive/2007/10/24/1840520.aspx
阿信
张沈鹏
>>> second_max = lambda x:heapq.nlargest(2,x)[-1]
>>> second_max([3,5,4,6])
5
我一直用它:)
张沈鹏
用一个union类型
+
一个变长数组
比如
http://blog.codingnow.com/2008/06/variable_length_array.html
也可以参考lua的代码
legendsland
1.如何在O(n)时间内找到一个整数数组中的第二大元素？
2.如何用c语言实现一个栈：
要求：1）栈的数据类型有多种，比如int，char或者函数指针等。
2）栈的大小不确定(即能够动态的分配空间)。
sjinny
恩……对时间复杂度的估算不太懂，也可能说得不对……
网易邮箱，中国第一大电子邮件服务商
emuer
用heapsort可以达到O(nlgn)
但既然是整数数组，可以用Quicksort-based selection来达到O(n)（参考<Algorithm in Java>原版
P342)
static ITEM select(ITEM [] a, int l, int r, int k)
{
while(r>l)
{
int i = partition(a, l ,r); //partition后，比a[i]小的都在i左边，比a[i]大的都在
i右边。
if(i==k) return a[k];
if(i<k) r=i-1; //从l到i-1做selection
if(i>k) l=i+1; //从i+1到r做selection
}
}
书中的证明是，对于足够大的随机数组，每次partion会把数组分成大约相等的两半，那么每次问题size缩小一般，比较次数为N+N/2+N/
4+.....+1=2N。因此为O(N)
注意select和quicksort不同，因为quicksort每次都要比较N，而select的比较次数是指数减少的，因此是O(N)而不是O
(NlgN)
在这里再推荐一下Segwick大牛的《Algorithm in Java》，真正的做到了从问题引出算法的教学形式，而不是版主说过的传统欧几里得
方法。
On 2月27日, 上午5时19分, talia <chao...@gmail.com> wrote:
> 1.如何在O(n)时间内找到一个整数数组中的第二大元素？
Fumin Shen
第一题，我首先想到的用位排序，编程珠玑上讲的第一个例子。
或者，用一个循环，循环的时候，一直保存两个变量（目前最大和第二大的数）。
Stephen
要求找出N个数中最大和最小两个数，问至少需要比较多少次？
针对这个问题，解法如下，对每一个数都有四种状态，N:从未比较过(没有信息)；L:曾经大过(1个信息)；S:曾经小过(1个信息)；W:曾经大过也
小过(2个信息)。于是，要取出最大数X和最小数Y，需要：
X (N-2) Y
S W L
1 2(N-2) 1
共1+2*(N-2)+1=2N-2个信息。
下面是各种数之间比较能产生的信息数：
N:N 产生2个信息；N:L,N:S,S:S,L:L,N:W各产生1个信息；S:W,L:W,W:W,S:L至多产生1个信息。
在比较的过程中，有[N/2]次N:N的比较，可获得2*[N/2]个信息。故还需要2(N-1)-2*[N/2]个信息，所以至少还需要比较这么多
次，所以
比较次数>=[N/2]+2(N-1)-2[N/2]＝2N-[N/2]-2=[3N/2]-2次。
第二题，不是很明白题目的要求1)。我的想法，其实可以模拟C++中的stack类，只不过没有类，自己维护一个内存空间。大致实现如下：
struct stack{
size_t width; //要保存数据的宽度，比如要保存int型的话，width=sizeof(int)
void *men; //保存栈元素的空间
void *bottom, *top;
size_t size; //已经分配的空间大小
//其他可能需要的元素
}
void InitStack(size_t w){
width = w; //这个值对这个栈而言不能再修改了
//分配一个适当大小的初始空间
}
void push(void *elem, size_t width){
//先判断当前空间是否足够
memcpy(top, elem, width);
top += width;
}
void *pop(){
return (top-=width);
}
用户通过pop取数时也是通过memcpy函数。
另外，如果题目要求的是同一个栈里面可以保存不同类型的元素，那么可以这样：
struct stack{
size_t *width_array; //用来保存栈中每个元素的width，由于栈的size随时会变，所以这个数组的空间也要动态分
配
size_t index; //用来保存栈中元素的个数，在push和pop时，可以用index从width_array这个数组中存入或取
出相应的width值
size_t used_size; //累计当前栈已用的空间
//剩下的部分省略，没什么难度了吧
}
On Feb 27, 9:19 pm, talia <chao...@gmail.com> wrote:
Fumin Shen
hack...@sina.com
第二题似乎是让你实现一个堆吧？
jrckkyy
小逗逗
--
Sincerely,
GongTao
Stephen
从题目的要求看，存入的元素的类型是未知的，可能是基本数据类型，也可能是个结构体，所以大小也是未知的。这点union就无能为力了，除非规定了元素类型只可能是确定的某几种数据类型。
而且题目并没有说存入的指针。如果存入的都是指针的话就好办了，只要把所有指针都转化为void*存入即可。但并没有这么要求。所以在这个栈中，所有每个元素占用的空间大小都要栈的实现者维护。
就像我昨晚发的那个帖子一样（昨晚发时用的是Stephen(zhang54112@126)这个邮箱，第一次发。加入这个Group一个月了，潜了一个月水。昨天发完后觉得还是改成真名好，同时现在这个邮箱用Gmail收取比原先那个更快些）。
言归正传，我觉得处理方法有点像C库函数中的qsort一样。qsort这个函数可以对任意类型的数据排序，声明如下：
void qsort(void *base, size_t width, size_t num, int (*compare)(const void*, const void*));
其中base是待排数组的首地址，width是每个元素的宽度，num是数组中元素的个数，compare是比较函数。
这里，qsort的实现并不关心具体的数据类型，也不关心数据之间的怎么比较大小。它关心的只是数据的宽度，以及数据间的大小关系（只要知道大小关系，但不要知道怎么比出来的）。数据的大小关系由qsort的用户给出，即compare函数。比如对一个double型数组排序，可以这么用：
qsort(base, sizeof(double), num, fcompare);
fcompare()函数由用户自己写:
int fcompare(const void *a, const void *b){
if(*(double*)a > *(double*)b)
return 1;
else if ..
return -1;
else
return 0;
}
之所以能这样实现，把qsort的实现的算法思想和具体操作分离开来，具体操作中，原子操作只有两个，移动数据和比较大小。对于移动数据，实现者只要知道数据的位置和width即可，不需要知道具体的数据类型，对于比较数据，实现者只需要知道两个元素的大小关系，而并不需要知道元素的具体类型和怎么比较。这样，qsort的实现就不依赖于具体的数据类型了。
这里栈的实现也是如此，实现者并不关心具体的数据类型，维护一个栈的原子操作就是复制/移动数据，而复制移动数据只需要知道数据的位置和宽度就可以用memcpy实现。
Cheng
0611 @ USTC
step...@mail.ustc.edu.cn
Sent from: Hefei 34 China.
--
Sincerely,
GongTao
Li Xunhao
你说得对，每一个stack frame由一个指针指向元素头和一个指明元素大小的变量，即可完全确定存入元素的内容。C这样的弱类型语言没办法知道读入的元素是什么类型，只能存元素内容。
2009/2/27 Stephen <step...@mail.ustc.edu.cn>:
--
Xunhao Li
A USTC Alumnus
Sent from: Edmonton Ab Canada.
Lei Yang
王晓轩
Stephen
用的是分治法。
Benjamin
int m = INT_MIN;
int n = INT_MIN;
while(...)
{
if (m < a[i])
{
n = m;
m = a[i];
talia
> 而且题目并没有说存入的指针。如果存入的都是指针的话就好办了，只要把所有指针都转化为void*存入即可。但并没有这么要求。所以在这个栈中，所有每个元素占-用的空间大小都要栈的实现者维护。
> 就像我昨晚发的那个帖子一样（昨晚发时用的是Stephen(zhang54112@126
> )这个邮箱，第一次发。加入这个Group一个月了，潜了一个月水。昨天发完后觉得还是改成真名好，同时现在这个邮箱用Gmail收取比原先那个更快些）。
> 言归正传，我觉得处理方法有点像C库函数中的qsort一样。qsort这个函数可以对任意类型的数据排序，声明如下：
> void qsort(void *base, size_t width, size_t num, int (*compare)(const void*,
> const void*));
> 其中base是待排数组的首地址，width是每个元素的宽度，num是数组中元素的个数，compare是比较函数。
> qsort(base, sizeof(double), num, fcompare);
> fcompare()函数由用户自己写:
> int fcompare(const void *a, const void *b){
> if(*(double*)a > *(double*)b)
> return 1;
> else if ..
> return -1;
> else
> return 0;}
>
> 这里栈的实现也是如此，实现者并不关心具体的数据类型，维护一个栈的原子操作就是复制/移动数据，而复制移动数据只需要知道数据的位置和宽度就可以用memcp-y实现。
>
> Cheng
> 0611 @ USTC
> steph...@mail.ustc.edu.cn
> Sent from: Hefei 34 China.
>
>
>
>
> > 第二题难道不是union或者链表么？（链表节点类型不定，指针可用void*再加类型转换）
>
> > 2009/2/28 hacke...@sina.com <hacke...@sina.com>
>
> >> 第一题是相当简单了。
> >> 第二题似乎是让你实现一个堆吧？
>
> >> On Feb 27, 5:19 am, talia <chao...@gmail.com> wrote:
> >> > 1.如何在O(n)时间内找到一个整数数组中的第二大元素？
> >> > 2.如何用c语言实现一个栈：
> >> > 要求：1）栈的数据类型有多种，比如int，char或者函数指针等。
> >> > 2）栈的大小不确定(即能够动态的分配空间)。
>
> >> > 先说我对第一题的想法：
> >> > 很yy的思路是：第一次循环找到最大值，第二次循环找到第二大值（不是最大值而大于其他值）。总时间是2n,
> >> > 算是O(n)的。
> >> > 另外一个想法是用基数排序，返回排序后的第二个位置的数值。总时间为O(cn)，c为这些数的最长位数。
>
> >> > 第二题。。。
>
> > --
> > Sincerely,
>
> - 显示引用的文字 -