a**********2 发帖数: 340 | 1 Given an array of integers where some numbers repeat 1 time, some numbers
repeat 2 times and only one number repeats 3 times, how do you find the
number that repeat 3 times. Using hash was not allowed
有什么巧解吗? |
c****p 发帖数: 6474 | 2 integer的值哉有什么限定么
【在 a**********2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given an array of integers where some numbers repeat 1 time, some numbers : repeat 2 times and only one number repeats 3 times, how do you find the : number that repeat 3 times. Using hash was not allowed : 有什么巧解吗?
|
c****p 发帖数: 6474 | 3 值域。。。
【在 c****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : integer的值哉有什么限定么
|
a**********2 发帖数: 340 | 4 32位吧
【在 c****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : integer的值哉有什么限定么
|
a**********2 发帖数: 340 | |
f*******t 发帖数: 7549 | 6 今天我面A家,三哥问了我这道题。
不过一开始是只有一个数出现奇数次,其它出现偶数次,我就说用异或解决。
然后他又换了个条件,一个数出现偶数次,其它出现奇数次,其实这个网上有用异或解
的代码,我一时实在找不出来,没看懂+记不住。提到hash他又说不能用,最终说了一
个暴力解法一个sort解法,他说sort就是想要的。 |
v***a 发帖数: 365 | 7
Sort 不就行了,integer 有好几个O(N)的sort吧
【在 a**********2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given an array of integers where some numbers repeat 1 time, some numbers : repeat 2 times and only one number repeats 3 times, how do you find the : number that repeat 3 times. Using hash was not allowed : 有什么巧解吗?
|
v********a 发帖数: 14 | 8 O(N)????
诚心求指点.
【在 v***a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : Sort 不就行了,integer 有好几个O(N)的sort吧
|
p*****2 发帖数: 21240 | 9
大牛给讲讲。
【在 v***a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : Sort 不就行了,integer 有好几个O(N)的sort吧
|
c****p 发帖数: 6474 | 10 我猜是counting sort
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 大牛给讲讲。
|
|
|
v***a 发帖数: 365 | 11
我不是大牛,只是提供的自己的想法,
bucket sort, radix sort, counting sort, 貌似都是O(N)的
http://en.wikipedia.org/wiki/Integer_sorting
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 大牛给讲讲。
|
c**********e 发帖数: 2007 | 12
Given sequence 1 10 100 1000 ...,which sort you mentioned is O(n)?
【在 v***a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我不是大牛,只是提供的自己的想法, : bucket sort, radix sort, counting sort, 貌似都是O(N)的 : http://en.wikipedia.org/wiki/Integer_sorting
|
t****y 发帖数: 27 | 13 similar to binary radix sort, from highest bit to lowest bit, and no
need to sort the lowest bit. This is an O(n) solution
numbers
【在 a**********2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given an array of integers where some numbers repeat 1 time, some numbers : repeat 2 times and only one number repeats 3 times, how do you find the : number that repeat 3 times. Using hash was not allowed : 有什么巧解吗?
|
k***t 发帖数: 276 | 14 可能是些初级问题:Binary Radix Sort 是O(N)还是O(NLogN)?
扫一遍,分两份,N,再对两份分别递归2*F(N/2)。
F(n)=2*F(n/2)+n 不是典型的O(NLogN)吗?
或者说是N*KeyBitLength,对4G个数是32N也等于N*Log(N)=N*Log(4G)=32N。
有何标准说法?
再有,递归时占用的栈空间算空间复杂时如何算?
请教了,谢谢。
【在 t****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : similar to binary radix sort, from highest bit to lowest bit, and no : need to sort the lowest bit. This is an O(n) solution : : numbers
|
k***t 发帖数: 276 | 15 看了一下,可能是这样。
Radix Sort:O(NumOfPassess*N)
Binary Radix Sort:NumOfPasses=LogN,当待排元素集接近所有穷尽时。
【在 k***t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可能是些初级问题:Binary Radix Sort 是O(N)还是O(NLogN)? : 扫一遍,分两份,N,再对两份分别递归2*F(N/2)。 : F(n)=2*F(n/2)+n 不是典型的O(NLogN)吗? : 或者说是N*KeyBitLength,对4G个数是32N也等于N*Log(N)=N*Log(4G)=32N。 : 有何标准说法? : 再有,递归时占用的栈空间算空间复杂时如何算? : 请教了,谢谢。
|
k***t 发帖数: 276 | 16 基本类似,只不过是Binary Radix Sort,而且是
从most-significant-digit(bit)开始。 |
t****y 发帖数: 27 | 17 Binary Radix Sort: #of bits *N
【在 k***t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看了一下,可能是这样。 : Radix Sort:O(NumOfPassess*N) : Binary Radix Sort:NumOfPasses=LogN,当待排元素集接近所有穷尽时。
|
t****y 发帖数: 27 | 18 The tree height is bounded to a constant value. so we cannot use mast theory
to analyze its complexity
【在 k***t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可能是些初级问题:Binary Radix Sort 是O(N)还是O(NLogN)? : 扫一遍,分两份,N,再对两份分别递归2*F(N/2)。 : F(n)=2*F(n/2)+n 不是典型的O(NLogN)吗? : 或者说是N*KeyBitLength,对4G个数是32N也等于N*Log(N)=N*Log(4G)=32N。 : 有何标准说法? : 再有,递归时占用的栈空间算空间复杂时如何算? : 请教了,谢谢。
|
TN 发帖数: 1870 | 19 clsr上典型阿,
【在 v********a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : O(N)???? : 诚心求指点.
|
k***t 发帖数: 276 | 20 这个题用大家说的(binary) Radix Sort的话,又没有shortcut在全部sort完前
提前判断重复3次的数?提前结束程序。
【在 a**********2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given an array of integers where some numbers repeat 1 time, some numbers : repeat 2 times and only one number repeats 3 times, how do you find the : number that repeat 3 times. Using hash was not allowed : 有什么巧解吗?
|
|
|
c*******g 发帖数: 8 | |
c*******g 发帖数: 8 | |
e***s 发帖数: 799 | 23
不解,不用SORT吧,BIT ARRAY 不行吗?
【在 f*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天我面A家,三哥问了我这道题。 : 不过一开始是只有一个数出现奇数次,其它出现偶数次,我就说用异或解决。 : 然后他又换了个条件,一个数出现偶数次,其它出现奇数次,其实这个网上有用异或解 : 的代码,我一时实在找不出来,没看懂+记不住。提到hash他又说不能用,最终说了一 : 个暴力解法一个sort解法,他说sort就是想要的。
|
z*y 发帖数: 1311 | 24
顶一个
没想到异或,确实牛
【在 c*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这么牛x的答案, 居然没人顶, 失望啊
|
s****a 发帖数: 528 | |