avatar
WIN 8 Setup 有什么建议?# Hardware - 计算机硬件
g*y
1
A/G都问的一道:Find kth smallest number in union of two sorted arrays
好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了,如果错了,请指正。
思路是用的ihasleetcode的:i+j=k, 既然k是固定的,那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的,稍改一下程序就行。
public int get(int[] a, int[] b, int k) {
int lower = Math.max(0, k-b.length-1);
int upper = Math.min(a.length-1, k-1);
int i = (lower + upper) / 2;
return get(a, b, k, lower, i, upper);
}
private int get(int[] a, int[] b, int k, int lower, int i, int upper) {
int j = k - i - 2;
if (j < 0) return Math.min(a[i], b[0]);
if (a[i] == b[j]) {
return a[i];
}
else if (a[i] < b[j]) {
if (i == upper) return b[j];
return get(a, b, k, i, (i+1+upper)/2, upper);
}
else { // a[i] > b[j]
if (i == lower) return a[i];
if (i == lower+1) return a[lower]>=b[j+1]? a[lower] : Math.min(a[i], b[j+1]);
return get(a, b, k, lower, (i-1+lower)/2, i);
}
}
avatar
b*2
2
rt。
以前在我们实验室待过,但我进组后他就走了,这样的不算。
曾经来我们实验室参观过,没有合作的,这样的也不算。
同一个学校的完全没合作过的,这样的还不算。
请问到底要怎样的人才算independent呢?痛苦啊,难道我一封独立的信都找不到吗?
大家说说找独立推荐人的经验吧。非常感谢!
avatar
D*k
3
我老终于被逼从WIN7升级
setup时候有什么要注意的?
有没有WIN10类似隐私方面的协议
avatar
i*e
4
很好的发现!赞!
你的想法是对的,在那里有读者曾在 comments 提出来。
There is an O(lg(min{m, n, k}) method. :-) FYI.
http://tanliboy.wordpress.com/2011/05/01/some-interesting-googl
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

错了,请指正。
然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的,稍改一下
程序就行。

【在 g**********y 的大作中提到】
: A/G都问的一道:Find kth smallest number in union of two sorted arrays
: 好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了,如果错了,请指正。
: 思路是用的ihasleetcode的:i+j=k, 既然k是固定的,那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的,稍改一下程序就行。
: public int get(int[] a, int[] b, int k) {
: int lower = Math.max(0, k-b.length-1);
: int upper = Math.min(a.length-1, k-1);
: int i = (lower + upper) / 2;
: return get(a, b, k, lower, i, upper);
: }
: private int get(int[] a, int[] b, int k, int lower, int i, int upper) {

avatar
v*l
5
看你怎么找了。如果老板可以帮你, 可以让老板发动他的狐朋狗友给你写。 如果自己
找, 一般可以是开会认识的,或者引用过你的文章的。晓之以理,动之以情,大多数
会给你写。也可以直接给业界的大牛写信,看能不能提携一下,这种就要看造化了。祝
好运!
avatar
F*r
6
必须上classic shell。谁用谁知道。

我老终于被逼从WIN7升级setup时候有什么要注意的?有没有WIN10类似隐私方面的协议

【在 D*******k 的大作中提到】
: 我老终于被逼从WIN7升级
: setup时候有什么要注意的?
: 有没有WIN10类似隐私方面的协议

avatar
g*y
7
哦,我没读comments, 原来早有人发现了 :)

【在 i**********e 的大作中提到】
: 很好的发现!赞!
: 你的想法是对的,在那里有读者曾在 comments 提出来。
: There is an O(lg(min{m, n, k}) method. :-) FYI.
: http://tanliboy.wordpress.com/2011/05/01/some-interesting-googl
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: 错了,请指正。
: 然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的,稍改一下
: 程序就行。

avatar
h*e
8

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
this one should be good.


【在 b**********2 的大作中提到】
: rt。
: 以前在我们实验室待过,但我进组后他就走了,这样的不算。
: 曾经来我们实验室参观过,没有合作的,这样的也不算。
: 同一个学校的完全没合作过的,这样的还不算。
: 请问到底要怎样的人才算independent呢?痛苦啊,难道我一封独立的信都找不到吗?
: 大家说说找独立推荐人的经验吧。非常感谢!

avatar
D*k
9
能否贡献地址?

【在 F********r 的大作中提到】
: 必须上classic shell。谁用谁知道。
:
: 我老终于被逼从WIN7升级setup时候有什么要注意的?有没有WIN10类似隐私方面的协议

avatar
s*y
10
O(lg(min{m, n, k})
m = 1; K = 10 n = 20;
so it will be lg m ?

【在 i**********e 的大作中提到】
: 很好的发现!赞!
: 你的想法是对的,在那里有读者曾在 comments 提出来。
: There is an O(lg(min{m, n, k}) method. :-) FYI.
: http://tanliboy.wordpress.com/2011/05/01/some-interesting-googl
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: 错了,请指正。
: 然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的,稍改一下
: 程序就行。

avatar
N*9
11
我是找引用我paper的人,把通讯联系人几乎全部联系了一遍,除了阿拉伯人。有两个
同意了,一个台湾,一个美国的,几率很低。开会的要了两个,也还不错。也有同学帮
找的一封。另外用公司的email联系比较好,不要用hotmail等。如果有人跟你老板或者
你单位某大牛比较熟,可以套套近乎,我这样搞到了唯一一封大牛的信。要推荐信和写
草稿是整个过程最头疼的过程,不过早晚要过,还是早点动。一旦开了头,就比较顺手
了。
祝你好运
avatar
g*y
12
对,答案只能是a[8], a[9], b[0]里的一个, 是常数次判断。

【在 s*****y 的大作中提到】
: O(lg(min{m, n, k})
: m = 1; K = 10 n = 20;
: so it will be lg m ?

avatar
l*9
13
我是找引用我的文章的人,还有就是nominated我的文章上F1000的,还有就是人家
follow我的文章继续做研究发文章了的人。



【在 b**********2 的大作中提到】
: rt。
: 以前在我们实验室待过,但我进组后他就走了,这样的不算。
: 曾经来我们实验室参观过,没有合作的,这样的也不算。
: 同一个学校的完全没合作过的,这样的还不算。
: 请问到底要怎样的人才算independent呢?痛苦啊,难道我一封独立的信都找不到吗?
: 大家说说找独立推荐人的经验吧。非常感谢!

avatar
g*0
14
you are right about the running time.
Thanks for sharing the code.

错了,请指正。
然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的,稍改一下
程序就行。

【在 g**********y 的大作中提到】
: A/G都问的一道:Find kth smallest number in union of two sorted arrays
: 好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了,如果错了,请指正。
: 思路是用的ihasleetcode的:i+j=k, 既然k是固定的,那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的,稍改一下程序就行。
: public int get(int[] a, int[] b, int k) {
: int lower = Math.max(0, k-b.length-1);
: int upper = Math.min(a.length-1, k-1);
: int i = (lower + upper) / 2;
: return get(a, b, k, lower, i, upper);
: }
: private int get(int[] a, int[] b, int k, int lower, int i, int upper) {

avatar
c*n
15
多谢分享
avatar
h*3
16
多谢分享。
我觉得还是有2个问题:
1)一个corner case: a[]={1} b[]={2}, 找第一个最小的,你的j会变成-1,溢出了
2) (i == upper-1) 只判断 Math.min(a[upper], b[j]);
是不够的, 一个例子
a[] = {1,2,3} b[]={4,5,6}, 找第4个最小的,你的程序似乎是返回 5 .
写了一个c的,欢迎指正。
int m_FindKthFromTwoSortedArray(int arr1[],int len1,int arr2[],int len2,int k)
{
int m1,m2;
int l1=max(0,k-len2-1),r1=min(len1-1,k-1);
if ( k == 1 )
return min(arr1[0],arr2[0]);
m1 = l1 + (r1-l1)/2;
m2 = k-(m1+1)-1;
while ( arr1[m1] != arr2[m2] && m1 <= min(len1-1,k-1) && m1 >= max(0,k-len2-1))
{
if ( arr1[m1] < arr2[m2] )
{
if( m1 == len1-1 || arr2[m2] <= arr1[m1+1] )
return arr2[m2];
else
l1 = m1+1;
}
else
{
if( m2 == len2-1 || arr1[m1] <= arr2[m2+1] )
return arr1[m1];
else if ( m1 == 0 )
return max(arr1[0],arr2[k-1]);
else
r1 = m1-1;
}
m1 = l1 + (r1-l1)/2;
if (m1 == k-1)
return min(arr1[m1],arr2[0]);
m2 = k - (m1+1)-1;
}
return arr2[m2];
}

错了,请指正。
然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的,稍改一下
程序就行。

【在 g**********y 的大作中提到】
: A/G都问的一道:Find kth smallest number in union of two sorted arrays
: 好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了,如果错了,请指正。
: 思路是用的ihasleetcode的:i+j=k, 既然k是固定的,那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的,稍改一下程序就行。
: public int get(int[] a, int[] b, int k) {
: int lower = Math.max(0, k-b.length-1);
: int upper = Math.min(a.length-1, k-1);
: int i = (lower + upper) / 2;
: return get(a, b, k, lower, i, upper);
: }
: private int get(int[] a, int[] b, int k, int lower, int i, int upper) {

avatar
g*y
17
谢谢指出错误,我写边界条件总容易出错,还是考虑不周密。

arr2[],int len2,int k)

【在 h*********3 的大作中提到】
: 多谢分享。
: 我觉得还是有2个问题:
: 1)一个corner case: a[]={1} b[]={2}, 找第一个最小的,你的j会变成-1,溢出了
: 2) (i == upper-1) 只判断 Math.min(a[upper], b[j]);
: 是不够的, 一个例子
: a[] = {1,2,3} b[]={4,5,6}, 找第4个最小的,你的程序似乎是返回 5 .
: 写了一个c的,欢迎指正。
: int m_FindKthFromTwoSortedArray(int arr1[],int len1,int arr2[],int len2,int k)
: {
: int m1,m2;

avatar
s*y
18
How about this one?
int Find_KthElement(int A[], int m, int B[], int n, int k)
{
if (k > m+n)
return 0;
if (m > n) {
return Find_KthElement(B,n,A,m,k);
}
int lo = 0;
int hi = min(m,k)-1;
while (lo < hi) {
int mid = lo + (hi-lo)/ 2;
int bIndex = k - mid - 2;
if (A[mid] < B[bIndex]) {
lo = mid +1;
} else {
hi = mid;
}
}
return max((A[lo] ? A[lo]:INT_MIN), (B[k-lo-2] ? B[k-lo-2]:INT_MIN));
}

arr2[],int len2,int k)

【在 h*********3 的大作中提到】
: 多谢分享。
: 我觉得还是有2个问题:
: 1)一个corner case: a[]={1} b[]={2}, 找第一个最小的,你的j会变成-1,溢出了
: 2) (i == upper-1) 只判断 Math.min(a[upper], b[j]);
: 是不够的, 一个例子
: a[] = {1,2,3} b[]={4,5,6}, 找第4个最小的,你的程序似乎是返回 5 .
: 写了一个c的,欢迎指正。
: int m_FindKthFromTwoSortedArray(int arr1[],int len1,int arr2[],int len2,int k)
: {
: int m1,m2;

avatar
h*3
19
你这个似乎有问题。
找最小的会溢出。
a[] = {1,2,3}
b[] = {4,5,6}
找第3小。

【在 s*****y 的大作中提到】
: How about this one?
: int Find_KthElement(int A[], int m, int B[], int n, int k)
: {
: if (k > m+n)
: return 0;
: if (m > n) {
: return Find_KthElement(B,n,A,m,k);
: }
: int lo = 0;
: int hi = min(m,k)-1;

avatar
s*y
20
Just try
K =1 return 1
K =3 return 3

【在 h*********3 的大作中提到】
: 你这个似乎有问题。
: 找最小的会溢出。
: a[] = {1,2,3}
: b[] = {4,5,6}
: 找第3小。

avatar
h*3
21
return max((A[lo] ? A[lo]:INT_MIN), (B[k-lo-2] ? B[k-lo-2]:INT_MIN));
k = 3 时候, k-lo-2 是-1, 溢出。
另外,a[]={1}, b[]={2}, 找最小也是溢出。

【在 s*****y 的大作中提到】
: Just try
: K =1 return 1
: K =3 return 3

avatar
s*y
22
Yes. You are right.
By luck I get the right answer even with this overflow.

【在 h*********3 的大作中提到】
: return max((A[lo] ? A[lo]:INT_MIN), (B[k-lo-2] ? B[k-lo-2]:INT_MIN));
: k = 3 时候, k-lo-2 是-1, 溢出。
: 另外,a[]={1}, b[]={2}, 找最小也是溢出。

avatar
g*y
23
hehe, 我发现这个题就是很难写边界条件,太简单的code, 几乎注定要倒在边界条件上。
Interview时写,怕是注定要写错。完全不出错,肯定会被怀疑是在默写code :)

【在 s*****y 的大作中提到】
: How about this one?
: int Find_KthElement(int A[], int m, int B[], int n, int k)
: {
: if (k > m+n)
: return 0;
: if (m > n) {
: return Find_KthElement(B,n,A,m,k);
: }
: int lo = 0;
: int hi = min(m,k)-1;

avatar
g*e
24
这个题,面试的时候要写对全部边界条件,我觉得几乎是不可能... 除非硬背

上。

【在 g**********y 的大作中提到】
: hehe, 我发现这个题就是很难写边界条件,太简单的code, 几乎注定要倒在边界条件上。
: Interview时写,怕是注定要写错。完全不出错,肯定会被怀疑是在默写code :)

avatar
p*a
25
简单讲一下这个的idea吧
没怎么看懂

错了,请指正。
然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的,稍改一下
程序就行。

【在 g**********y 的大作中提到】
: A/G都问的一道:Find kth smallest number in union of two sorted arrays
: 好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了,如果错了,请指正。
: 思路是用的ihasleetcode的:i+j=k, 既然k是固定的,那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的,稍改一下程序就行。
: public int get(int[] a, int[] b, int k) {
: int lower = Math.max(0, k-b.length-1);
: int upper = Math.min(a.length-1, k-1);
: int i = (lower + upper) / 2;
: return get(a, b, k, lower, i, upper);
: }
: private int get(int[] a, int[] b, int k, int lower, int i, int upper) {

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。