由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 帮着看到G家题
相关主题
1G内存读10G文件O(lgk)解法Find the k-th Smallest in Two Sorted Arrays
请教一道题目问个google面试题
请问一个老的google题Given two sorted list, find the k smallest number (binary search)
amazon 电面题amazon面试题目讨论贴
amazon phone interview讨论做题:find kth smallest number in two sorted arrays at
两个Sorted Array,找K smallest element问题:Find the minimum number of "swaps" needed to sort an array
一道热门的 Google 面试题Find the Kth smallest element in 2 sorted
问道面试题关于求the kth smallest in two sorted array
相关话题的讨论汇总
话题: sorted话题: belong话题: sum话题: given话题: smallest
进入JobHunting版参与讨论
1 (共1页)
s****r
发帖数: 28
1
Given two sorted postive integer arrays A(n) and B(n),each array is
decreased order sorted. find n smallest sum of pair of (a, b), a belong to A
, b belong to B
Is there a O(n) algorithm ?
c********t
发帖数: 5706
2
我觉得没有O(n)解

A

【在 s****r 的大作中提到】
: Given two sorted postive integer arrays A(n) and B(n),each array is
: decreased order sorted. find n smallest sum of pair of (a, b), a belong to A
: , b belong to B
: Is there a O(n) algorithm ?

M********5
发帖数: 715
3
我对这道题没有很明白,能否给个解释?

【在 c********t 的大作中提到】
: 我觉得没有O(n)解
:
: A

c********t
发帖数: 5706
4
我理解是找最小的 n个 sum. sum是指 a+b

【在 M********5 的大作中提到】
: 我对这道题没有很明白,能否给个解释?
l******n
发帖数: 9344
5


【在 c********t 的大作中提到】
: 我理解是找最小的 n个 sum. sum是指 a+b
c******g
发帖数: 1
6
直接用merge 有什么问题吗?
每次比较A[i]+B[j+1]和A[i+1]和B[j]

A

【在 s****r 的大作中提到】
: Given two sorted postive integer arrays A(n) and B(n),each array is
: decreased order sorted. find n smallest sum of pair of (a, b), a belong to A
: , b belong to B
: Is there a O(n) algorithm ?

s****n
发帖数: 147
7
感觉可以直接找a和b中Na+Nb个smallest数
Na是a中最小的若干数
Nb是b中最小的若干数
Na * Nb = n
1 (共1页)
进入JobHunting版参与讨论
相关主题
关于求the kth smallest in two sorted arrayamazon phone interview
有更好的解法吗?Kth smallest element in a row-wise and column-wise sorted 2D array两个Sorted Array,找K smallest element
一道G家题一道热门的 Google 面试题
A家面试题问道面试题
1G内存读10G文件O(lgk)解法Find the k-th Smallest in Two Sorted Arrays
请教一道题目问个google面试题
请问一个老的google题Given two sorted list, find the k smallest number (binary search)
amazon 电面题amazon面试题目讨论贴
相关话题的讨论汇总
话题: sorted话题: belong话题: sum话题: given话题: smallest