g****v 发帖数: 971 | 1 我对真个算法都非常清楚,唯一不明白的是些实现问题:
怎样去保存曾经比较过的数字。
比如:
5 4 2 6 -1 -5 7 8
先找到最小的数字是-5,然后需要在和它比较过的数字中找个最小的,想知道怎样找到去比
较过的数字?
谢谢 |
g****v 发帖数: 971 | |
s*****y 发帖数: 897 | 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******e 发帖数: 2265 | 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****v 发帖数: 971 | 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****v 发帖数: 971 | 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*********i 发帖数: 197 | 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. |