由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Given an int array and an int value. Find all pairs in arr
相关主题
A面经问道题,谁给个效率高点的解法
HashTable space complexity?请教个面试题
问一个面试题问一道面试题目
A家新鲜面经--都是经典题求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)
关于Hash_map也问一个算法题
水果电面问题 hashmap 用 sperate chaining 时, array size不够怎么办这题怎么做?
Google电话面试题目5分钟前G的电面
Given an array of N integers from range [0, N] and one is missing. Find the missing number.a[i] + b[j] = c[k] 的题有靠谱的答案不?
相关话题的讨论汇总
话题: integer话题: num话题: int话题: array话题: sum
进入JobHunting版参与讨论
1 (共1页)
j**y
发帖数: 462
1
array 5,3,7,5,12,5,5
sum 10
output
5,5
3,7
5,5
5,5
5,5
5,5
5,5
no O(n^2)
Thanks
h*********3
发帖数: 111
2

用hash就可以了。
但不明白为什么只有5对 5,5, 应该是6对吧 。

【在 j**y 的大作中提到】
: array 5,3,7,5,12,5,5
: sum 10
: output
: 5,5
: 3,7
: 5,5
: 5,5
: 5,5
: 5,5
: 5,5

A*****i
发帖数: 3587
3
n2是指n^2么?
用一个hash table存每一个元素的配对值,需要o(n),
然后遍历hash table一旦配对值hits, 就将相配的俩数拿出来,这也需要o(n)
一共0(2n)
j**y
发帖数: 462
4
对 是6对
讲讲hash 怎么做吗?多谢

【在 h*********3 的大作中提到】
:
: 用hash就可以了。
: 但不明白为什么只有5对 5,5, 应该是6对吧 。

j**y
发帖数: 462
5

5,3,7,5,12,5,5 -> 5,7,3,5,-5,5,5, 然后呢?

【在 A*****i 的大作中提到】
: n2是指n^2么?
: 用一个hash table存每一个元素的配对值,需要o(n),
: 然后遍历hash table一旦配对值hits, 就将相配的俩数拿出来,这也需要o(n)
: 一共0(2n)

r*******y
发帖数: 1081
6
hash table怎么处理重复的数呢?

【在 A*****i 的大作中提到】
: n2是指n^2么?
: 用一个hash table存每一个元素的配对值,需要o(n),
: 然后遍历hash table一旦配对值hits, 就将相配的俩数拿出来,这也需要o(n)
: 一共0(2n)

A*****i
发帖数: 3587
7


【在 r*******y 的大作中提到】
: hash table怎么处理重复的数呢?
c*****l
发帖数: 879
8
排序 前后2指针遍历下不就行了?
j**y
发帖数: 462
9
得到6对? 5,5

【在 c*****l 的大作中提到】
: 排序 前后2指针遍历下不就行了?
j**y
发帖数: 462
10
还是没有答案?多谢了
相关主题
水果电面问题 hashmap 用 sperate chaining 时, array size不够怎么办问道题,谁给个效率高点的解法
Google电话面试题目请教个面试题
Given an array of N integers from range [0, N] and one is missing. Find the missing number.问一道面试题目
进入JobHunting版参与讨论
m********l
发帖数: 4394
11

重看了下, 你的问题好像没说清楚
不过试试用Chained Hash了吗?
1) create the hash table.
2) create a link-list node that stores the position of the value
3) put the values inside the hash table. Preferably, during insertion,
you want LIFO
4) loop thru the array again
4.1) get hash[sum-value]
4.2) print if the position of the hash value is greater than current
value's position.
4.3) if position > node->position, continue;
=============
Yes, it's a hack.
why do they test you on procedural stuff when all they teach you in
school is OOP?

【在 j**y 的大作中提到】
: 还是没有答案?多谢了
g**e
发帖数: 6127
12
let me give u an example, 5,5,5,5,5,5; sum=10
there is no way to do it less than O(n^2). This is the worst case.
this structure will help you: HashMap>

【在 j**y 的大作中提到】
: 还是没有答案?多谢了
g***s
发帖数: 3811
13
i dont know why Hashmap doesn't work. maybe i mis-
understand the question?
void findPairs(int[] array, int sum) {
HashMap map = new HashMap();
for (int num : array){
if (map.containsKey(sum - num)){
for (int i = 0; i< map.get(sum-num); i++){
System.out.println(num + "," + (sum-num));
}
}
map.put(num, map.containsKey(num)? map.get(num)+1 : 1);
}
}
the time is O(n+L) L is the pair num of output.
if L<
g**e
发帖数: 6127
14
是我看错题了,我以为要输出所有index呢,所以value用了个LinkedList
原来只是输出元素就可以了

【在 g***s 的大作中提到】
: i dont know why Hashmap doesn't work. maybe i mis-
: understand the question?
: void findPairs(int[] array, int sum) {
: HashMap map = new HashMap();
: for (int num : array){
: if (map.containsKey(sum - num)){
: for (int i = 0; i< map.get(sum-num); i++){
: System.out.println(num + "," + (sum-num));
: }
: }

j**y
发帖数: 462
15
thanks

【在 g***s 的大作中提到】
: i dont know why Hashmap doesn't work. maybe i mis-
: understand the question?
: void findPairs(int[] array, int sum) {
: HashMap map = new HashMap();
: for (int num : array){
: if (map.containsKey(sum - num)){
: for (int i = 0; i< map.get(sum-num); i++){
: System.out.println(num + "," + (sum-num));
: }
: }

1 (共1页)
进入JobHunting版参与讨论
相关主题
a[i] + b[j] = c[k] 的题有靠谱的答案不?关于Hash_map
求这道题的O(N)解 (转载)水果电面问题 hashmap 用 sperate chaining 时, array size不够怎么办
算法题:两列找共同元素有O(n)的算法吗?Google电话面试题目
新鲜Amazon面经Given an array of N integers from range [0, N] and one is missing. Find the missing number.
A面经问道题,谁给个效率高点的解法
HashTable space complexity?请教个面试题
问一个面试题问一道面试题目
A家新鲜面经--都是经典题求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)
相关话题的讨论汇总
话题: integer话题: num话题: int话题: array话题: sum