R***r
发帖数: 120 | 1 无意中看到这道题，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? | C**********n
发帖数: 100 | 2 是不是问两个数组都是由同样的数字组成？
【在 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?
| S**Y
发帖数: 136 | 3 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?
| g*******y
发帖数: 1930 | 4 本来觉得这类题要提高时间性能，用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?
| R***r
发帖数: 120 | 5 对
【在 C**********n 的大作中提到】
: 是不是问两个数组都是由同样的数字组成？
| C**********n
发帖数: 100 | 6 以前见过一个家伙说过
可以两个数组互减，然后将差相加，如果为0，则相同。
比如a=[1,3,6,4],b=[6,1,4,3]
差为［-5,2,2,1］，相加为0。
这种方法对否?
【在 R***r 的大作中提到】
: 对
| S**Y
发帖数: 136 | 7 cant u just verify?
[0 0 0 0]
[2 2 -2 -2]
[-2 -2 2 2] sum = 0
do u think they equal?
【在 C**********n 的大作中提到】
: 以前见过一个家伙说过
: 可以两个数组互减，然后将差相加，如果为0，则相同。
: 比如a=[1,3,6,4],b=[6,1,4,3]
: 差为［-5,2,2,1］，相加为0。
: 这种方法对否?
| g*******y
发帖数: 1930 | 8 ft
这个只是判断了两个数组的和相等啊
另外，这题关于duplicate的数字是怎么要求的?
比如，A ={1,2,2}
B ={1,2}
是否output true？
【在 C**********n 的大作中提到】
: 以前见过一个家伙说过
: 可以两个数组互减，然后将差相加，如果为0，则相同。
: 比如a=[1,3,6,4],b=[6,1,4,3]
: 差为［-5,2,2,1］，相加为0。
: 这种方法对否?
| C**********n
发帖数: 100 | 9 是不是还得用一个数组表示各个数字用了多少次?
【在 g*******y 的大作中提到】
: ft
: 这个只是判断了两个数组的和相等啊
: 另外，这题关于duplicate的数字是怎么要求的?
: 比如，A ={1,2,2}
: B ={1,2}
: 是否output true？
| S**Y
发帖数: 136 | 10 i guess not hehe
【在 g*******y 的大作中提到】
: ft
: 这个只是判断了两个数组的和相等啊
: 另外，这题关于duplicate的数字是怎么要求的?
: 比如，A ={1,2,2}
: B ={1,2}
: 是否output true？
| | | f**e
发帖数: 1269 | 11 把两个数组的数字都xor起来，如果等于0的话就return true。
【在 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?
| S**Y
发帖数: 136 | 12 still not correct.
easy find counter cases
【在 f**e 的大作中提到】
: 把两个数组的数字都xor起来，如果等于0的话就return true。
| N*D
发帖数: 3641 | 13 ft
【在 f**e 的大作中提到】
: 把两个数组的数字都xor起来，如果等于0的话就return true。
| s********y
发帖数: 3811 | 14 set1: 22
set2: 11
【在 f**e 的大作中提到】
: 把两个数组的数字都xor起来，如果等于0的话就return true。
| g*******y
发帖数: 1930 | 15 yes只能说明 A 并 B的集合里面，每个元素都出现了偶数次
当然，如果你明确的知道A，B中的元素都是unique的话，这个方法可以。
【在 S**Y 的大作中提到】
: still not correct.
: easy find counter cases
| o*o
发帖数: 404 | 16 像这种要求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?
| f*********r
发帖数: 68 | 17 我认为可以从"例证法"考虑. 因为集合中的数都是整数, 找到最大最小值后, 先比较,
如果不同, 原集合不一样, 否则的话, 可以根据这两个最值找一个或几个数(floating
point), 然后和每一个集合中的数相减, 然后计算差的平方和, 判断是否相等. 至于
这几个用来例证的数怎么找, 有些trick, 还没有完全想明白. | z***e
发帖数: 5393 | 18 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
发帖数: 1280 | 19 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)
|
|
