无意中看到这道题,google了一下竟然发现很多提问但没一个可靠的答案,大家帮忙看 看。 Given two arrays of numbers, find if each of the two arrays have the same set of integers? Suggest an algo which can run faster than NlogN without extra space?
r*e
3 楼
7000 points 2800 points + $45 $79 + tax 选哪个?
y*i
4 楼
大家好,最近在给我父母办理B2签证。想问一些问题。 先简单介绍一下情况,我小孩(一岁半)在国内给我爸妈带。这次打算把小孩接过来。 我爸妈之前来过几次美国都是B签证,签证都很顺利,最近一次也是在2015年2月来的8 月走的。 但是小孩已经在国内呆了将近一年了,所以想如果直接我去接,小孩可能不适应。想我 爸妈也一起过来。这里有些问题。 Q1:这种情况,是不是就可以免面谈,直接寄到广州,对吧?在填写申请地方就写广州 对吧。 Q2: 如果我不回去,让我爸妈接过来可否,我听说过之前有的入境处移民官会觉得B2不 是来旅游而是带孩子,会刁难。但是我也有同学的小孩就是他爸妈(爷爷奶奶)带过来 ,好像也没有啥事情。不过我可能还是倾向于自己回去和我爸妈一起吧小孩接过来。这 样可能保险一些,请问大家我的理解正确吗 Q3: 我在给他们办理签证的时候,有个问题 Enter person(s) traveling with you Surnames of Person Traveling With You Given Names of Person Traveling With You 这个GIVEN NAME,小孩是英 文名字,那是写 FIRST NAME和MIDDLE NAME都要写吗? MIDDLE NAME可以简写吗 Relationship with Person Click here for more information 这个关系是指陪同着对于申请人的关系吗?比如说签证申请人是我妈,然后我也会和我 爸妈一起走,然后我就会列在这里,那么这个关系是写 CHILD,还是 PARENT呢 暂时这些个问题,谢谢大家告知一下。
【在 R***r 的大作中提到】 : 无意中看到这道题,google了一下竟然发现很多提问但没一个可靠的答案,大家帮忙看 : 看。 : Given two arrays of numbers, find if each of the two arrays have the same : set of integers? Suggest an algo which can run faster than NlogN without : extra space?
o(1) space and o(n) time? doesn't seem possible...
【在 R***r 的大作中提到】 : 无意中看到这道题,google了一下竟然发现很多提问但没一个可靠的答案,大家帮忙看 : 看。 : Given two arrays of numbers, find if each of the two arrays have the same : set of integers? Suggest an algo which can run faster than NlogN without : extra space?
本来觉得这类题要提高时间性能,用hash是很好的。不过要求不用extra space,难道用in place 开放寻址的hashing?
【在 R***r 的大作中提到】 : 无意中看到这道题,google了一下竟然发现很多提问但没一个可靠的答案,大家帮忙看 : 看。 : Given two arrays of numbers, find if each of the two arrays have the same : set of integers? Suggest an algo which can run faster than NlogN without : extra space?
谢谢回复 Q1 请问我如果回去接,然后和父母一起过来。这样问题不大吧? Q2 还有给问题,Do you have any immediate relatives, not including parents in the U.S.? 这个要写孙子吗?但是孙子还是在国内现在。然后我看了看上次的签证DS160也 没有写我老婆。这个算IMMEDIATE RELATIVE吗?好像选项里面没有。
【在 y**i 的大作中提到】 : 谢谢回复 : Q1 请问我如果回去接,然后和父母一起过来。这样问题不大吧? : Q2 还有给问题,Do you have any immediate relatives, not including parents in : the : U.S.? 这个要写孙子吗?但是孙子还是在国内现在。然后我看了看上次的签证DS160也 : 没有写我老婆。这个算IMMEDIATE RELATIVE吗?好像选项里面没有。 : : 见:
【在 y**i 的大作中提到】 : 谢谢回复 : Q1 请问我如果回去接,然后和父母一起过来。这样问题不大吧? : Q2 还有给问题,Do you have any immediate relatives, not including parents in : the : U.S.? 这个要写孙子吗?但是孙子还是在国内现在。然后我看了看上次的签证DS160也 : 没有写我老婆。这个算IMMEDIATE RELATIVE吗?好像选项里面没有。 : : 见:
【在 R***r 的大作中提到】 : 无意中看到这道题,google了一下竟然发现很多提问但没一个可靠的答案,大家帮忙看 : 看。 : Given two arrays of numbers, find if each of the two arrays have the same : set of integers? Suggest an algo which can run faster than NlogN without : extra space?
yes只能说明 A 并 B的集合里面,每个元素都出现了偶数次 当然,如果你明确的知道A,B中的元素都是unique的话,这个方法可以。
【在 S**Y 的大作中提到】 : still not correct. : easy find counter cases
o*o
67 楼
像这种要求without extra space,是指不能用任何temporary变量吗? 比如求和的sum。
【在 R***r 的大作中提到】 : 无意中看到这道题,google了一下竟然发现很多提问但没一个可靠的答案,大家帮忙看 : 看。 : Given two arrays of numbers, find if each of the two arrays have the same : set of integers? Suggest an algo which can run faster than NlogN without : extra space?
actually don't need to use b-search, you can make decision while sorting. find a common number, using quick sort, the firt iteration will divide to: A: array1, array2 B: array1, array2 if (A.array1.size == B.array1.size && A.array2.size == B.array2.size) recursively do this until the array size is different. if A == B, the complexity is at most O(nlgn) (quick sort); otherwise it's smaller. so the total complexity <=O(nlgn)
c*l
70 楼
find a common number?
【在 z***e 的大作中提到】 : actually don't need to use b-search, you can make decision while sorting. : find a common number, using quick sort, the firt iteration will divide to: : A: array1, array2 : B: array1, array2 : if (A.array1.size == B.array1.size && A.array2.size == B.array2.size) : recursively do this until the array size is different. : if A == B, the complexity is at most O(nlgn) (quick sort); : otherwise it's smaller. : so the total complexity <=O(nlgn)