作者bleed1979 (十三)
看板C_and_CPP
标题[问题] 一维阵列中最长位置连续但数值相异整数
时间Wed Apr 29 10:45:34 2009
想请教在不用STL的情况下, 也就是以C语言来解有没有更好的演算法
一维阵列：1, 2, 4, 3, 1, 5
最长位置连续但数值相异整数序列为 2, 4, 3, 1, 5
思考上有几个限制
限制1.不能使用STL(用Map解就很快了)
限制2.整数最小为1, 最大到10^9(动态宣告即使是char也会超出规定的记忆体限制)
限制3.一定是位置连续相异(不太能排序解, 排序解适用位置不连续的情况)
限制4.阵列长度为100万个
我的演算法为
分成左指标和右指标
左指标代表序列开头, 右指标依序向右递增
如果右指标指到的数可以在两个指标之间(含左指标, 不含右指标)找到的话
设一个变数代表最长相异序列的长度, 小於右指标 - 左指标 + 1 就更新其值
左指标更新为指向找到位置 + 1
这个演算法耗费大量时间在找两个指标之间的数
因为连续相异我只得用循序的方式查找
最差情况是O(n^2)
请教更高效率的演算法
Bleed
--
World of bleed1979
http://bleed1979.myweb.hinet.net/
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.168.133.60
1F：→ maplefog:请问什麽是最长连续相异整数，又连续又相异? 04/29 10:55
2F：推 Ebergies:连续是指位置连续, 相异是指数字相异 04/29 10:57
3F：推 jlovet:後项减前项,差不等於1的就记下来 04/29 11:27
4F：→ jlovet:找最长得不等於一的 04/29 11:27
5F：→ bleed1979:我修改一下标题和原文 以免看的人误会了 04/29 11:31
※ 编辑: bleed1979 来自: 118.168.133.60 (04/29 11:34)
6F：推 Ebergies:三楼这样会找到 1 2 4 3 1 5 04/29 11:34
7F：→ Ebergies:看来只是误会题目 XDD 04/29 11:35
8F：→ jlovet:喔喔,我知道你的意思了 04/29 11:46
9F：推 Ebergies:我的建议是弄个 hash 再用你 "很快" 的方法解 04/29 11:48
10F：→ adrianshum:赞同楼上... 不用 STL, 也能做 hashtable/map 之类呀 04/29 11:54
11F：推 ledia:假设答案是 k, 你可以 O(n) 验证有没有长度 k 的答案 04/29 12:03
12F：→ ledia:binary search k, 整个问题的复杂度就是 O(kn), 不用 hash 04/29 12:03
13F：→ ledia:更正.... 验证还是要用 hash 04/29 12:04
14F：→ ledia:不然会变成 O(klgk * n) 04/29 12:04
15F：推 ledia:不用 hash 的验证方式是用一个 heap 变形, 每次 len-k 的 04/29 12:06
16F：→ ledia:咦 我想错了 囧 再想想... 04/29 12:07
17F：→ ledia:是 bst node 记次数才对.... 04/29 12:07
18F：推 chrisdar:两个指标 O(N*N) 验证指标内有没有重复O(N) 总共O(N^3) 04/29 12:11
19F：→ bleed1979:感谢大家 我现在正朝着hash table的方向努力 04/29 14:52
20F：→ bleed1979:有结果再上来po文 04/29 14:52
21F：推 gba356:限四这个数据（一百万）应该是要求 O(NlgN) 以下的意思吧？ 04/29 16:36