※ 引述《bleed1979 (十三)》之铭言： : 想请教在不用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 sorry~ 我有点搞混了 它的意思是 在他给的 1D array中 从[1]开始 连续取值 到一个set中 直到不能insert到set中为止 的长度 称作 从[1]开始的(相异)雪花数量 对吧? so 从开头[1]~[10^6] 每一个都算出雪花数量後 找出最大的雪花数量 称作 最大(相异)雪花数量 对吗? --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 118.166.122.53