m**********w
发帖数: 60 | 1 小弟请教一道电面题：
给一个整数数组， 找到其中包含最多连续数的子集，
比如给：15, 7, 12, 6, 14, 13, 9, 11
则返回: 5:[11, 12, 13, 14, 15]
最简单的方法是sort然后scan一遍，但是要o(nlgn). 有什么O(n)的方法吗？ | c********w
发帖数: 2438 | 2 另开一个大的数组b
把原来数组a里有的数做大数组的index
b[a[i]]都设为1
其余为0
然后统计？
可以么？ | p*****2
发帖数: 21240 | | m**********w
发帖数: 60 | | p*****2
发帖数: 21240 | 5
我在想一下。
【在 p*****2 的大作中提到】
: map+interval
| m**********w
发帖数: 60 | 6 我的思路跟你差不多，我用bitmap，但是这样需要很多内存，看起来很笨拙，不知道有
没有啥好方法~
【在 c********w 的大作中提到】
: 另开一个大的数组b
: 把原来数组a里有的数做大数组的index
: b[a[i]]都设为1
: 其余为0
: 然后统计？
: 可以么？
| p*****2
发帖数: 21240 | 7 val arr=Array(15, 7, 12, 6, 14, 13, 9, 11)
val map=collection.mutable.Map[Int,Array[Int]]()
var start=0
var end=0
for(i<-0 until arr.length){
if(!map.contains(arr(i)))
map(arr(i))=Array[Int](arr(i),arr(i))
if(map.contains(arr(i)-1))
map(arr(i))(0)=map(arr(i)-1)(0)
if(map.contains(arr(i)+1))
map(arr(i))(1)=map(arr(i)+1)(1)
map(map(arr(i))(0))(1)=map(arr(i))(1)
map(map(arr(i))(1))(0)=map(arr(i))(0)
if(map(arr(i))(1)-map(arr(i))(0)>end-start){
start=map(arr(i))(0)
end=map(arr(i))(1)
}
}
println(start to end mkString(",")) | e****e
发帖数: 418 | 8 I think sort+scan is a good approach. If there is a range for the value of
elements, then bitmap is good too.
Time complexity.
The first one is nlog(n).
Second one is n+k. k is the size of the range.
Depending on the the characteristics/property/pattern of data in the array,
choose one of the two approaches. | p*****2
发帖数: 21240 | 9
,
两个都不是O(n)复杂度呀。
【在 e****e 的大作中提到】
: I think sort+scan is a good approach. If there is a range for the value of
: elements, then bitmap is good too.
: Time complexity.
: The first one is nlog(n).
: Second one is n+k. k is the size of the range.
: Depending on the the characteristics/property/pattern of data in the array,
: choose one of the two approaches.
| e****e
发帖数: 418 | 10 二爷说说你的代码的思路吧，我没有看懂你的代码。。。
【在 p*****2 的大作中提到】
:
: ,
: 两个都不是O(n)复杂度呀。
| | | p*****2
发帖数: 21240 | 11
就是保存interval, 保存头尾，然后merge头尾，同时更新结果
【在 e****e 的大作中提到】
: 二爷说说你的代码的思路吧，我没有看懂你的代码。。。
| h**6
发帖数: 4160 | 12 想起来前几年一道竞赛题，求最短连续数串的最长长度。
那题跟打麻将差不多，有时候需要牺牲较长数串，帮助较短数串延伸长度。 | e****e
发帖数: 418 | 13 有点明白了,谢二爷解释.
当遍历到13的时候，map的样子(仅显示相关的pair):
15 -> {15, 15}
12 -> {12, 12}
14 -> {14, 15}
遍历完13之后是什么样子？
遍历完11之后是什么样子？
如果还有一个数是16, 遍历完16之后是什么样子？
【在 p*****2 的大作中提到】
:
: 就是保存interval, 保存头尾，然后merge头尾，同时更新结果
| p*****2
发帖数: 21240 | 14
loop:0
15:15,15
loop:1
7:7,7
15:15,15
loop:2
7:7,7
12:12,12
15:15,15
loop:3
7:6,7
12:12,12
6:6,7
15:15,15
loop:4
14:14,15
7:6,7
12:12,12
6:6,7
15:14,15
loop:5
14:14,15
13:12,15
7:6,7
12:12,15
6:6,7
15:12,15
loop:6
14:14,15
13:12,15
7:6,7
9:9,9
12:12,15
6:6,7
15:12,15
loop:7
11:11,15
14:14,15
13:12,15
7:6,7
9:9,9
12:12,15
6:6,7
15:11,15
loop:8
11:11,16
14:14,15
13:12,15
16:11,16
7:6,7
9:9,9
12:12,15
6:6,7
15:11,15
answer:
11,12,13,14,15,16
【在 e****e 的大作中提到】
: 有点明白了,谢二爷解释.
: 当遍历到13的时候，map的样子(仅显示相关的pair):
: 15 -> {15, 15}
: 12 -> {12, 12}
: 14 -> {14, 15}
: 遍历完13之后是什么样子？
: 遍历完11之后是什么样子？
: 如果还有一个数是16, 遍历完16之后是什么样子？
| m**********w
发帖数: 60 | 15 明白你的思路了，膜拜二爷。 我面试时想到往interval上靠，就是没想明白怎么merge
来着的， 唉
【在 p*****2 的大作中提到】
:
: loop:0
: 15:15,15
: loop:1
: 7:7,7
: 15:15,15
: loop:2
: 7:7,7
: 12:12,12
: 15:15,15
| B*******1
发帖数: 2454 | 16 Disjoint set. Union find
★ 发自iPhone App: ChineseWeb 7.8
【在 m**********w 的大作中提到】
: 小弟请教一道电面题：
: 给一个整数数组， 找到其中包含最多连续数的子集，
: 比如给：15, 7, 12, 6, 14, 13, 9, 11
: 则返回: 5:[11, 12, 13, 14, 15]
: 最简单的方法是sort然后scan一遍，但是要o(nlgn). 有什么O(n)的方法吗？
| p*****2
发帖数: 21240 | 17
merge
我刚才就是想这个来着。当时感觉应该可以，但是也没想太清楚。
【在 m**********w 的大作中提到】
: 明白你的思路了，膜拜二爷。 我面试时想到往interval上靠，就是没想明白怎么merge
: 来着的， 唉
| e****e
发帖数: 418 | 18 明白了，我喜欢这个思路，简单多谢二爷！
【在 p*****2 的大作中提到】
:
: merge
: 我刚才就是想这个来着。当时感觉应该可以，但是也没想太清楚。
| e****e
发帖数: 418 | 19 关于优化空间的一点浅见.
如果没有duplicate存在，每次merge之后，可以删除值位于中间的entry, 他们的value
(interval)也不准确，留着以后也用不上，例如loop7里，可以从map里删除key为12,13
,14的entry.如果连续数目多，这样做可以节省大量空间。
有duplicate这个优化空间的思路就不行了!
诸位大牛的看法？ | c**1
发帖数: 71 | 20 a O(n) algorithm:
max_count=0
build a hash map for all the numbers
traverse the original list, for each number i {
if it does not exist in hash map {
continue
} else {
x = i, count = 1
delete x from hashmap
while --x is in hashmap {
delete x from hashmap
++count
}
x=i
while ++x is in hashmap {
delete x from hashmap
++count
}
if count > max_count
max_count = count
}
}
return max_count | | | p*****2
发帖数: 21240 | 21
这个思路不错。写起来要简单很多。
【在 c**1 的大作中提到】
: a O(n) algorithm:
: max_count=0
: build a hash map for all the numbers
: traverse the original list, for each number i {
: if it does not exist in hash map {
: continue
: } else {
: x = i, count = 1
: delete x from hashmap
: while --x is in hashmap {
| f*******t
发帖数: 7549 | | s*****n
发帖数: 5488 | 23 not good.
for all big array things, can be solved by prefix tree too.
【在 c********w 的大作中提到】
: 另开一个大的数组b
: 把原来数组a里有的数做大数组的index
: b[a[i]]都设为1
: 其余为0
: 然后统计？
: 可以么？
| s*****n
发帖数: 5488 | 24 1. 1-5
2. 1-5
0-7
3. 1-5
1-2
0-7
4. 1-5
1-2
0-[6-7] 2
5. 1-[4-5] 2
1-2
0-[6-7] 2
6. 1-[2-5] 4
0-[6-7] 2
7. 1-[2-5] 4
0-9
0-[6-7] 2
8 1-[1-5] 5
0-9
0-[6-7]
you need to build a prefix radius tree and with sibling link at the leaf
level then merge with prev and next when you insert a new int into the tree.
this solution has O(n) time and 32*n space.
【在 m**********w 的大作中提到】
: 小弟请教一道电面题：
: 给一个整数数组， 找到其中包含最多连续数的子集，
: 比如给：15, 7, 12, 6, 14, 13, 9, 11
: 则返回: 5:[11, 12, 13, 14, 15]
: 最简单的方法是sort然后scan一遍，但是要o(nlgn). 有什么O(n)的方法吗？
| f*******l
发帖数: 66 | 25 C++里面没有hashmap， 需要现场写个hash 函数吗？
【在 p*****2 的大作中提到】
:
: 这个思路不错。写起来要简单很多。
| j*****y
发帖数: 1071 | 26 unordered_map
【在 f*******l 的大作中提到】
: C++里面没有hashmap， 需要现场写个hash 函数吗？
| c*u
发帖数: 22 | 27 第一次循环把数存到HashSet
第二次循环对HashSet删减，记录最大数
最后输出
C#
int[] array = { 8, 15, 5, 7, 12, 6, 14, 13, 9, 11, 8 };
HashSet set = new HashSet();
foreach (int val in array)
if (!set.Contains(val))
set.Add(val);
int min = 0, max = 0, maxCount = 0;
while (set.Count > 0)
{
int left = 0, right = 0, count = 1;
int val = set.First();
int now = val + 1;
while (set.Contains(now))
{
count++;
set.Remove(now);
now++;
}
right = now - 1;
now = val - 1;
while (set.Contains(now))
{
count++;
set.Remove(now);
now--;
}
left = (val == now) ? val : now + 1;
if (maxCount < count)
{
maxCount = count;
min = left;
max = right;
}
set.Remove(val);
}
for (int i = min; i <= max; i++)
Console.WriteLine("{0} ", i);
【在 m**********w 的大作中提到】
: 小弟请教一道电面题：
: 给一个整数数组， 找到其中包含最多连续数的子集，
: 比如给：15, 7, 12, 6, 14, 13, 9, 11
: 则返回: 5:[11, 12, 13, 14, 15]
: 最简单的方法是sort然后scan一遍，但是要o(nlgn). 有什么O(n)的方法吗？
|
|
