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 的大作中提到】
: 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 的大作中提到】
: integer的值哉有什么限定么
|
a**********2
发帖数: 340 | 4 32位吧
【在 c****p 的大作中提到】
: integer的值哉有什么限定么
|
a**********2
发帖数: 340 | |
f*******t
发帖数: 7549 | 6 今天我面A家，三哥问了我这道题。
不过一开始是只有一个数出现奇数次，其它出现偶数次，我就说用异或解决。
然后他又换了个条件，一个数出现偶数次，其它出现奇数次，其实这个网上有用异或解
的代码，我一时实在找不出来，没看懂+记不住。提到hash他又说不能用，最终说了一
个暴力解法一个sort解法，他说sort就是想要的。 |
v***a
发帖数: 365 | 7
Sort 不就行了，integer 有好几个O(N)的sort吧
【在 a**********2 的大作中提到】
: 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 的大作中提到】
:
: Sort 不就行了，integer 有好几个O(N)的sort吧
|
p*****2
发帖数: 21240 | 9
大牛给讲讲。
【在 v***a 的大作中提到】
:
: Sort 不就行了，integer 有好几个O(N)的sort吧
|
c****p
发帖数: 6474 | 10 我猜是counting sort
【在 p*****2 的大作中提到】
:
: 大牛给讲讲。
|
|
|
v***a
发帖数: 365 | 11
我不是大牛，只是提供的自己的想法，
bucket sort, radix sort, counting sort, 貌似都是O(N)的
http://en.wikipedia.org/wiki/Integer_sorting
【在 p*****2 的大作中提到】
:
: 大牛给讲讲。
|
c**********e
发帖数: 2007 | 12
Given sequence 1 10 100 1000 ...,which sort you mentioned is O(n)?
【在 v***a 的大作中提到】
:
: 我不是大牛，只是提供的自己的想法，
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 可能是些初级问题：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 的大作中提到】
: 看了一下，可能是这样。
: 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 的大作中提到】
: 可能是些初级问题：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 的大作中提到】
: O(N)????
: 诚心求指点.
|
k***t
发帖数: 276 | 20 这个题用大家说的(binary) Radix Sort的话，又没有shortcut在全部sort完前
提前判断重复3次的数？提前结束程序。
【在 a**********2 的大作中提到】
: 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 的大作中提到】
: 今天我面A家，三哥问了我这道题。
: 不过一开始是只有一个数出现奇数次，其它出现偶数次，我就说用异或解决。
: 然后他又换了个条件，一个数出现偶数次，其它出现奇数次，其实这个网上有用异或解
: 的代码，我一时实在找不出来，没看懂+记不住。提到hash他又说不能用，最终说了一
: 个暴力解法一个sort解法，他说sort就是想要的。
|
z*y
发帖数: 1311 | 24
顶一个
没想到异或，确实牛
【在 c*******g 的大作中提到】
: 这么牛x的答案, 居然没人顶, 失望啊
|
s****a
发帖数: 528 | |
