|
f****4
发帖数: 1359 | 2 原帖：http://www.mitbbs.com/article_t/Programming/31198701.html
Two reverse sorted arrays A and B have been given.such that size of A is m
and size of B is n You need to find the k th largest sum (a+b) where a is
taken from A and b is taken from B. such that k < m*n
有O(n)的解么？怎么转化成杨矩啊？
谢谢 |
|
l*****a
发帖数: 14598 | 3 为什么非往矩阵上靠
跟N有什么关系？
assume求最小的吧
obviously a[0]+b[0] is the least
we can create a minimum heap with the size of k
each time ,pop up the smallest as a[i]+b[j]
then we can insert a[i+1]+B[j],a[i]+b[j+1] into the heap
each time adjust the heap need lgk
we need to do k times.
so time complexity will be O(klgk)
another tricky here,think about it at first |
|
f****4
发帖数: 1359 | 4 k
最坏的情况： n=m，k=n^2，你的方法是O(n^2*lgn)
我问的是有没有O(n)的解法。
有人说能转换成杨矩，有点不明白：对一个满的n*m杨矩，有O(n)的解法找到第k大数么？ |
|
H****s
发帖数: 247 | 5 貌似这题O(n)不大可能， 我也想知道O(n)的解法， 帮顶！ |
|
|
|
f****4
发帖数: 1359 | 8 能够解释一下么？
这个link，在49匹马的赛马题里面已经有人给过了
不过在这怎么用？
谢谢 |
|
f****4
发帖数: 1359 | 9 Median of Medians algorithm
就是这个wiki的例子，当47找到之后，如果我们是要找第80大的数，
是不是要把大于47的数中，再找第32大数（重新按5行分列，重新计算medians，再算
median of medians）。直到找到那个数？
但是49匹马的赛马题能套这个方法，但我不能证明这个办法赛马次数最少。。。 |
|
f****4
发帖数: 1359 | 10 找到一个对的O(N)的解法
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
This is a pretty good puzzle. You can actually find the cutoff and a
description of exactly which pairs are in the solution in less than O(N)
time, but outputting all the solutions takes O(N) time, so it doesn't help
you overall. This won't be much of a hint, but finding the cutoff point can
be done in O(sqrt(N)*log2N) time. Forgive me for not writing code, but this
gets pretty nitty-gritty in spots.
I think of the pro... 阅读全帖 |
|
g*****i
发帖数: 2162 | 11 只有2个数组的话不需要用heap吧,就每个数组维系1个pointer,当前最大值是a[i]+b[j]
的话,第二大值只会在a[i]+b[j+1]或者a[i+1]b[j]里面产生,只有一个pointer要移动 |
|
|
B*******1
发帖数: 2454 | 13 可否仔细解释一下这哥们的算法啊，看得很晕，不知道他说啥。
thanks
can
this
formed |
|
r*******h
发帖数: 315 | 14 多显然的一道题，还要什么矩阵。既然a和b都已经降序排列，直接p=k/n取上整，如果p
==1，直接从b中取第k个和a最大相加，如果p>1，q=k mod n，取a中第p个和b中第q个相
加。 |
|
e***s
发帖数: 799 | 15 不会吧。。。
你的解是在b最大的元素小于a最小的元素才成立吧。
果p |
|
h*z
发帖数: 33 | 16 根据Young tableau的思路下了以下算法。
写的有点罗嗦。简单说就是在Young tableau里保持两个索引(a,b), (c,d), a >= c, b
<= d, 这两个中有一个是第k步最大的和。下面有些condition case省略了不可能的情
况。第4步，k是一个常数。25行O(m)。可以把横竖换一下变成O(n)。
M(x, y)
1 return A[x] + B[y]
LARGEST(k)
1 (a, b) = (1, 1)
2 (c, d) = (1, 1)
3 (e, f) = (1, 1)
4 for i = 1 to k
5 if a = c and b = d then
6 (e, f) = (a, b)
7 if a = m and b = n then
8 // last element, stop
9 else if a = m and b < n then
10 (a, b) = (1, b + 1)
11 (c, d) = (1, d + 1)
1... 阅读全帖 |
|
f****4
发帖数: 1359 | 17 没仔细看，不过你想维护2个索引来找第k大sum是不对的
楼上有说，第k大sum的可能对象是线性增加的
b |
|
|
h*z
发帖数: 33 | 19 的确不对。
现在有另外一个想法：
我们知道每一行中，从大到小排序的。假设我们已经找到k-1个最大的数，这k-1个数必
然是靠左上角的。也就是以下形状：x表示确定了，也就是前k-1个最大数。
xxxxo-
xxo---
xo----
o-----
下一个最大数必然在o中间产生，也就是每一行没有确定的，最大的那个数。一共n行，
所以O(kn)=O(n)。 |
|
x*******7
发帖数: 223 | 20 到底怎么答好呢？leetcode上面找中位数和找kth解法好像不一样吧。 |
|
c****p
发帖数: 6474 | 21 method 1: use a generic equation.
method 2: recursive way
GC(0) = 0, GC(1) = 1;
GC(2^k + n) = 2^k + GC(2^k-n-1), where 0<=n<=2^k-1
in other words, to get GC for 2^k to 2^(k+1)-1, flip the GC sequence of 0~2^
k-1, and set the kth bit(LSB is 0th bit).
000
001
--- k = 1, flip and set 1st bit
011
010
--- k = 2, flip and set 2nd bit
110
111
101
100
--- ..... |
|
|
r*****k
发帖数: 1281 | 23 1 find kth element in two sorted arrays.
2 write a function to implement aligned memory allocation.
阿三面的，我第一题只给出o(k)的结果，第二题也写的不利索。挂了。我太弱了，还是
要练熟经典题啊！！
★ 发自iPhone App: ChineseWeb - 中文网站浏览器 |
|
C*********u
发帖数: 116 | 24 迷糊第一题，既然是array，读Kth element不是O（1），直接就找到了吗？为啥我看不
懂题目. :( |
|
r*****k
发帖数: 1281 | 25 1 find kth element in two sorted arrays.
2 write a function to implement aligned memory allocation.
阿三面的，我第一题只给出o(k)的结果，第二题也写的不利索。挂了。我太弱了，还是
要练熟经典题啊！！
★ 发自iPhone App: ChineseWeb - 中文网站浏览器 |
|
C*********u
发帖数: 116 | 26 迷糊第一题，既然是array，读Kth element不是O（1），直接就找到了吗？为啥我看不
懂题目. :( |
|
g****y
发帖数: 240 | 27 尝试着写了一下第一题：
def findk(alist, blist, k):
"""Given two sorted array, find kth minimum element"""
m = len(alist)
n = len(blist)
assert (k <= m + n)
if m == 0:
return blist[k - 1]
elif n == 0:
return alist[k - 1]
if k == 1:
return min(alist[0], blist[0])
# divide k into two even parts as much as possible
ai = min(k // 2, m)
bi = k - ai
if bi > n:
bi = n
ai = k - bi
if alist[ai - 1] == blist... 阅读全帖 |
|
w********0
发帖数: 2 | 28 试着写了一下，好像可以，没有仔细测试。
public class FindKthFromTwoArray{
public static void main(String[] args)
{
int[] a = {2,4,6,7,8,10,19,20,24,98};
int[] b = {2,5,15,18,27,34,56,67,100,140};
// int[] a = {2,4,19,29,39,49,59};
// int[] b = {1,5,6,7,12,29,30,33,45,67,78};
// int[] a = {2};
// int[] b = {1};
int k = 16;
int result = FindKthFromTwoArray.findKth(a,b,k);
System.out.println("The kth number is: " + result);
}
p... 阅读全帖 |
|
a*****n
发帖数: 158 | 29 我解释了，说如果重复的数字出现在Kth位置，检查的次数为K。 |
|
m**a
发帖数: 139 | 30 放到一个{value,index}的struct里面然后再处理？ 比较大小只比较value。
办？ |
|
|
p*i
发帖数: 411 | 32 #include
#include
#include
#include
using namespace std;
inline void swap(int &a, int &b) {
int t = a; a = b; b = t;
}
int partition(vector& work, vector& indices, int p, int q) {
// use work[q] to partition the array
const int x = work[q];
int i = p-1;
for (int j = p; j < q; j++) {
if (work[j] < x) {
i++;
swap(work[i], work[j]);
swap(indices[i], indices[j]);
}
}
i++;... 阅读全帖 |
|
g***j
发帖数: 1275 | 33 请问你的程序里面第k小，是从多少开始的？ 第一个是k 为0还是k为1
这个partition返回的r是index吧？
如果k 的最小值为 1，就是最小的值
这句话不对吧？
int r = partition(work, indices, p, q);
if (r-p == k) return indices[r];
个人觉得应该是
if (r-p+1 == k) return indices[r]; |
|
p*i
发帖数: 411 | 34 main里面k从1开始，符合人的习惯
int pos = find_kthsmallest(A, k-1); <-- 我传了k-1
其它函数都是c++默认的从0开始，符合语言本身习惯
虽然这样没有必要。 |
|
|
g***j
发帖数: 1275 | 36 记得班上讨论过这个题目，但是1379code上面的似乎看起来很麻烦
请问有谁有好的想法么？ |
|
|
|
p*****i
发帖数: 197 | 39 来自主题: JobHunting版 - 问道算法题 题目是：
How to find the kth largest element in an unsorted array of length n in O(n)
? |
|
s******n
发帖数: 3946 | 40 停好的题目练手：数组a大小m，数组b大小n，两个数组从大到小排序。求第kth大的sum(a[i],a[j])，0
15, 4, 3, 2, 1
5, 4, 2, 1 |
|
C***U
发帖数: 2406 | 41 #include
#include
#include
#define MAX 10000
int main(int argc, char *argv[]){
std::vector numbers1;
std::vector numbers2;
int k = atoi(argv[3]);
if(argc < 4)
std::cout << "we need 2 files and a number." << std::endl;
std::cout << "we need find " << k << "th number" << std::endl;
std::cout << "reading first array of numbers ..." << std::endl;
std::ifstream f1(argv[1]);
if(!f1){
std::cout << "cannot open... 阅读全帖 |
|
C***U
发帖数: 2406 | 42 自己顶
有大牛帮忙看看
对不对 有啥需要改进的？ |
|
z****4
发帖数: 194 | 43 我在wiki上看到的是这个：
Despite being an easy to understand concept, computing the geometric median
poses a challenge. The centroid or center of mass, defined similarly to the
geometric median as minimizing the sum of the squares of the distances to
each sample, can be found by a simple formula — its coordinates are the
averages of the coordinates of the samples — but no such formula is known
for the geometric median, and it has been shown that no explicit formula,
nor an exact algorithm involving only a... 阅读全帖 |
|
w****x
发帖数: 2483 | 44 迭代法:
//Find the nth number which is composed by factor 2, 3 and 5
void PrintSerials(int n)
{
assert(n > 0);
vector vec;
vec.push_back(1);
int nI2 = 0;
int nI3 = 0;
int nI5 = 0;
int nCount = 1;
while(nCount < n)
{
int nTmp2 = vec[nI2]*2;
int nTmp3 = vec[nI3]*3;
int nTmp5 = vec[nI5]*5;
int nMin = min(min(nTmp2, nTmp3), nTmp5);
if (vec.back() != nMin)
{
vec.push_back(nMin);
nCount++;
... 阅读全帖 |
|
|
l******e
发帖数: 149 | 46 wwwyhx 的解法还是很牛的，简化了一下
static List getNth235(int k){
int i2 = 0, i3 = 0, i5 = 0;
List list = new ArrayList();
list.add(1);
while(list.size() < k){
int n2 = list.get(i2)*2;
int n3 = list.get(i3)*3;
int n5 = list.get(i5)*5;
int tmp = Math.min(Math.min(n2, n3), n5);
list.add(tmp);
if(tmp == n2) i2++;
if(tmp == n3) i3++;
if(tmp == n5) i5++;
}
return list;
} |
|
c**********e
发帖数: 2007 | 47 Good solutions. Thank you both. |
|
w****o
发帖数: 2260 | 48 wwwyhx,
没有完全看懂，能否讲讲你的idea?
你用了三个index, nI2, nI3, nI5,然后不断的调整这些index,到底每个index都指示的
是什么？
careercup 150题的哪本书上，是用了3个queue,你的做法和careercup的做法是如何等
效的？
其实这两个我都没有完全弄明白。
谢谢！ |
|
w****o
发帖数: 2260 | 49 好像不对的。我试了一下 2, 3, 5 的情况，是错的。 |
|
|
