details 2nd smallest element in an array - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

details 2nd smallest element in an array

details 2nd smallest element in an array# JobHunting - 待字闺中

g*v2011-06-07 07:06

1 楼

我对真个算法都非常清楚，唯一不明白的是些实现问题：
怎样去保存曾经比较过的数字。
比如：
5 4 2 6 -1 -5 7 8
先找到最小的数字是-5，然后需要在和它比较过的数字中找个最小的，想知道怎样找到去比
较过的数字？
谢谢

g*v2011-06-07 07:06

2 楼

难道需要保存每一个element的比较对象么

s*y2011-06-07 07:06

3 楼

int smallest = INT_MAX;
int second_smallest = INT_MAX;
for (int i = 0; i < sizeof(input)/sizeof(int);i++) {
if (second_smallest < input[i]) {
if (smallest < input[i]) {
second_smallest = smallest ;
smallest = input[i];
} else {
second_smallest = input[i];
}
}
}
return second_smallest;

d*e2011-06-07 07:06

4 楼

You sure?
5 4 2 6 -1 -5 7 8
4 2 -1 -5
-1 -5
第一轮 4次比较，第二轮 6次比较，第三轮3次比较。

到去比

【在 g****v 的大作中提到】

: 我对真个算法都非常清楚，唯一不明白的是些实现问题：
: 怎样去保存曾经比较过的数字。
: 比如：
: 5 4 2 6 -1 -5 7 8
: 先找到最小的数字是-5，然后需要在和它比较过的数字中找个最小的，想知道怎样找到去比
: 较过的数字？
: 谢谢

g*v2011-06-07 07:06

5 楼

最优算法是n+lgn-2. CLR书上的一个课后题。

【在 s*****y 的大作中提到】

: int smallest = INT_MAX;
: int second_smallest = INT_MAX;
: for (int i = 0; i < sizeof(input)/sizeof(int);i++) {
: if (second_smallest < input[i]) {
: if (smallest < input[i]) {
: second_smallest = smallest ;
: smallest = input[i];
: } else {
: second_smallest = input[i];
: }

g*v2011-06-07 07:06

6 楼

应该是这样：
5 4 2 6 -1 -5 7 8
4 2 -5 7
2 -5
-5
然后再在{2,7,-1}中找最小的，但现在问题是怎样得到{2,7,-1}

【在 d******e 的大作中提到】

: You sure?
: 5 4 2 6 -1 -5 7 8
: 4 2 -1 -5
: -1 -5
: 第一轮 4次比较，第二轮 6次比较，第三轮3次比较。
:
: 到去比

f*i2011-06-07 07:06

7 楼

In this case, every element is unique, therefore, a possible way is to
create a hashtable which for each element, which contains all the numbers it
compared before.
Hashtable>
therefore, it is O(logn) approach, but we need O(n) space.