由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - details 2nd smallest element in an array
相关主题
请教一道题目求个4sum的算法
find Kth Largest Element 有没有更简化的解法O(N) sort integer array
真慫阿, Facebook 1st phone interview,amazon phone interview
向各位大侠请教几道面试题的思路攒人品,twitter二面面经
Given an array of N integers from range [0, N] and one is missing. Find the missing number.C++ Q78: about sizeof
求这道题的O(N)解 (转载)关于质数(prime number)的算法题
google youtube interview, 莫名被拒。。。。。。leetcode上遇到的问题
请问一个老的google题kth smallest element
相关话题的讨论汇总
话题: smallest话题: int话题: element话题: input话题: second
进入JobHunting版参与讨论
1 (共1页)
g****v
发帖数: 971
1
我对真个算法都非常清楚,唯一不明白的是些实现问题:
怎样去保存曾经比较过的数字。
比如:
5 4 2 6 -1 -5 7 8
先找到最小的数字是-5,然后需要在和它比较过的数字中找个最小的,想知道怎样找到去比
较过的数字?
谢谢
g****v
发帖数: 971
2
难道需要保存每一个element的比较对象么
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.
1 (共1页)
进入JobHunting版参与讨论
相关主题
kth smallest elementGiven an array of N integers from range [0, N] and one is missing. Find the missing number.
说一下上周五狗狗家的面试另外求祝福求这道题的O(N)解 (转载)
CS: print all combination from an arraygoogle youtube interview, 莫名被拒。。。。。。
问个算法题请问一个老的google题
请教一道题目求个4sum的算法
find Kth Largest Element 有没有更简化的解法O(N) sort integer array
真慫阿, Facebook 1st phone interview,amazon phone interview
向各位大侠请教几道面试题的思路攒人品,twitter二面面经
相关话题的讨论汇总
话题: smallest话题: int话题: element话题: input话题: second