BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ aiwei (天天上上) 于 (Thu Jul 29 13:54:00 2010) 提到: 一个int数列，int a[]={x1,x2,..,xi,..,xn}; 若该数列中每个元素后面小于该元素的元素严格降序，则为符合条件的数列。请问给定一个数列，判断是否为符合条件的数列。 ☆─────────────────────────────────────☆ jmpesp (卡实冻袂条~~ ) 于 (Thu Jul 29 14:09:28 2010) 提到: 【在 aiwei 的大作中提到: 】 : 一个int数列，int a[]={x1,x2,..,xi,..,xn}; 若该数列中每个元素后面小于该元素的元素严格降序，则为符合条件的数列。请问给定一个数列，判断是否为符合条件的数列。这个貌似没啥问题吧时间O(n) 空间O(1) ☆─────────────────────────────────────☆ shenlei (我爱果子|[路]|天山南北|潇湘隐士) 于 (Thu Jul 29 14:11:14 2010) 提到: 1和2比较,2和3比较,3和4比较...有一个不符合整体就不符合了...这个莫非还有别的好算法? ☆─────────────────────────────────────☆ jmpesp (卡实冻袂条~~ ) 于 (Thu Jul 29 14:11:59 2010) 提到: 【在 shenlei 的大作中提到: 】 : 1和2比较,2和3比较,3和4比较...有一个不符合整体就不符合了...这个莫非还有别的好算法? 不可能了更好的算法了 O(n)是下限 ☆─────────────────────────────────────☆ Wing () 于 (Thu Jul 29 16:26:53 2010) 提到: 【在 shenlei 的大作中提到: 】 : 1和2比较,2和3比较,3和4比较...有一个不符合整体就不符合了...这个莫非还有别的好算法? : -- : ┌─├──┐┌ ─┐ ┌────┐ 路过路过也要有道德 : ................... 每个元素后面小于该元素的数严格降序，你这个是整个数列严格降序吧...... ☆─────────────────────────────────────☆ zxsword (YNWA) 于 (Thu Jul 29 16:32:28 2010) 提到: C版人气好强大 Java和算法都有人来问=。= ☆─────────────────────────────────────☆ dyrdyr (bitren@bupt) 于 (Thu Jul 29 18:29:53 2010) 提到: 先判断是不是比该元素小，在比较就可以了【在 Wing 的大作中提到: 】 : 每个元素后面小于该元素的数严格降序，你这个是整个数列严格降序吧...... ☆─────────────────────────────────────☆ aiwei (天天上上) 于 (Thu Jul 29 22:22:08 2010) 提到: 咋比较，菜鸟求问。【在 dyrdyr 的大作中提到: 】 : 先判断是不是比该元素小，在比较就可以了 ☆─────────────────────────────────────☆ aiwei (天天上上) 于 (Thu Jul 29 22:23:57 2010) 提到: 不是整个数列严格降序，比如4,8,3,2,1。【在 Wing 的大作中提到: 】 : 每个元素后面小于该元素的数严格降序，你这个是整个数列严格降序吧...... ☆─────────────────────────────────────☆ Wing () 于 (Fri Jul 30 08:57:30 2010) 提到: 【在 aiwei 的大作中提到: 】 : 不是整个数列严格降序，比如4,8,3,2,1。 : 【在 Wing 的大作中提到: 】 : : 每个元素后面小于该元素的数严格降序，你这个是整个数列严格降序吧...... : ................... 我知道，我是说1和2比较,2和3比较,3和4比...这种方法只能判断整个数列降序 ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Fri Jul 30 10:09:13 2010) 提到: 【在 aiwei 的大作中提到: 】 : 一个int数列，int a[]={x1,x2,..,xi,..,xn}; 若该数列中每个元素后面小于该元素的元素严格降序，则为符合条件的数列。请问给定一个数列，判断是否为符合条件的数列。 : -- 线段树吧。需要一个结构，保存当前的“不可能区域”。所谓“不可能区域，就是如果下一个的数落在这个区域，整个数列就不符合要求。如图，每个点表示一个数，横坐标是出现的顺序，纵坐标表示每个数的大小，越高越大。涂色的部分是”不可能区域“。每次加一个点，需要保证新点不落在当前的”不可能区域“内，而且还会产生新的”不可能区域“，新的”不可能区域“的范围是从当前最大的点，到这个新的点的范围。新的“不可能区域”需要和原有的区域合并。“不可能区域”的总范围只能越来越大。 [upload=1][/upload] ☆─────────────────────────────────────☆ dynamic (dynamic) 于 (Fri Jul 30 11:41:35 2010) 提到: 【在 aiwei 的大作中提到: 】 : 一个int数列，int a[]={x1,x2,..,xi,..,xn}; 若该数列中每个元素后面小于该元素的元素严格降序，则为符合条件的数列。请问给定一个数列，判断是否为符合条件的数列。 : -- 倒过来比较怎么样，用动态规划的思路，时间O(n)，空间O(1)应该能解决吧。 ☆─────────────────────────────────────☆ jackbupt (jackbupt) 于 (Fri Jul 30 13:04:57 2010) 提到: 【在 aiwei 的大作中提到: 】 : 一个int数列，int a[]={x1,x2,..,xi,..,xn}; 若该数列中每个元素后面小于该元素的元素严格降序，则为符合条件的数列。请问给定一个数列，判断是否为符合条件的数列。敢问此题是LZ命的吗？鄙人认为此题不用判断，任何情况都成立。因为条件“每个元素后面小于该元素的元素严格降序”，既然只是挑小于的数，那么当然严格降序了。 ☆─────────────────────────────────────☆ duvet (蕾丝乳酪) 于 (Fri Jul 30 13:18:02 2010) 提到: 路过，反例：4、1、2、3 【在 jackbupt 的大作中提到: 】 : 敢问此题是LZ命的吗？鄙人认为此题不用判断，任何情况都成立。因为条件“每个元素后面小于该元素的元素严格降序”，既然只是挑小于的数，那么当然严格降序了。 ☆─────────────────────────────────────☆ buptss (buptss) 于 (Fri Jul 30 14:45:38 2010) 提到: <遍历数列中所有元素，对其中每个元素作如下操作 <读入每个元素本身，(O(1))。通过比较，将比它小的所有元素取出，填到一新增数组中O(n) <判断该数组是否严格递减（如是，跳出）O(n)> > 继续遍历> 直到最后一个元素。这种方法的空间复杂度O(n),时间复杂度O(2n*n) ☆─────────────────────────────────────☆ shunshine (shine) 于 (Fri Jul 30 20:29:21 2010) 提到: 【在 buptss 的大作中提到: 】 : <遍历数列中所有元素，对其中每个元素作如下操作 : <读入每个元素本身，(O(1))。通过比较，将比它小的所有元素取出，填到一新增数组中O(n) : <判断该数组是否严格递减（如是，跳出）O(n)> : ................... 这个时间复杂度是O（n^2）吧 ☆─────────────────────────────────────☆ Andier (La.is.la.bonita) 于 (Sat Jul 31 04:30:52 2010) 提到: 动态规划靠谱。这样应该可以： upperBound = max(a[1]...a[N]) or a sufficiently large number // O(N) minSeen = max(a[1]...a[N]) or a sufficiently large number // O(N) 从i=N-1向前比较 if a[i]>upperBound 则说明测试失败。整个序列不符合要求，return false else if a[i]<=a[i+1] upperBound = min(a[i+1],upperBound, mininum) // 再往前的数不能小于a[i+1] minimum = a[i]; else if a[i]>a[i+1] // do nothing 一直到了第一个元素还没问题，Return true. 时间O(N), 空间O(1) upperbound是从后向前数，出现的所有上升序列中，第二小的数，而不是最小那个。因为如果再往前有大于最小，但小于第二小的数，并没有关系。 minSeen 是所有见过数中最小的。如果a[i]<a[i+1]的时候，上界应该等于a[i+1]和minSeen里面比较小的那个。这样才能确保它(算上a[i])是第二小的。修改了一下，还是觉得有点纠结。欢迎大家拍砖。。 p.s. 多谢wks的回复。 ☆─────────────────────────────────────☆ richlm (银剑山庄) 于 (Sun Aug 1 11:22:24 2010) 提到: 不错的扫描算法。【在 Andier 的大作中提到: 】 : 动态规划靠谱。这样应该可以： : upperBound = max(a[1]...a[N]) or a sufficiently large number // O(N) : 从i=N-1向前比较 : ................... ☆─────────────────────────────────────☆ RaulSpain007 (Raul) 于 (Mon Aug 2 10:44:31 2010) 提到: 【在 jmpesp 的大作中提到: 】 : 不可能了更好的算法了 O(n)是下限如果是判断整个数列为严格递减还真有...用分治的思想应该可以降到logn ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Mon Aug 2 11:29:08 2010) 提到: 【在 Andier 的大作中提到: 】 : 动态规划靠谱。这样应该可以： : upperBound = max(a[1]...a[N]) or a sufficiently large number // O(N) : 从i=N-1向前比较 : ................... 反例：6,3,7,5,9 开始： upperBound = 9 对于5： 5<=9, upperBound = min(9,upperBound) = 9 对于7: 7>9, do nothing 对于3: 3<=7, upperBound = min(7, upperBound) = 7 对于6： 6>3, do nothing 结果：接受6,3,7,5,9 但是，6后面有3,5。不符合要求。 ☆─────────────────────────────────────☆ jmpesp (卡实冻袂条~~ ) 于 (Mon Aug 2 11:31:10 2010) 提到: 【在 wks 的大作中提到: 】 : 反例：6,3,7,5,9 : 开始： : upperBound = 9 : ................... zz 每次wks回帖我就能學到一點什麽 ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Mon Aug 2 13:54:25 2010) 提到: 其实谁回帖你都能学到点什么【在 jmpesp 的大作中提到: 】 : : 【在 wks 的大作中提到: 】 : : 反例：6,3,7,5,9 : ................... ☆─────────────────────────────────────☆ gootyking (『热情一顶乐团』团长|回帖终结者A1) 于 (Mon Aug 2 13:58:14 2010) 提到: 除了我。。。呃。，【在 wks (cloverprince) 的大作中提到: 】 : 其实谁回帖你都能学到点什么 ☆─────────────────────────────────────☆ SuK (木有~) 于 (Mon Aug 2 14:33:57 2010) 提到: 想了2分钟，不一定好用哈，只是提供一种思路：反过来呢，从最后一个数开始，往前找，对于每一个数，如果前面有数大于他，设has_bigger=1，如果有数小于他，设has_smaller=1,如果遍历完整个数列不满足 has_bigger && has_smaller，那么对前一个数开始遍历，否则return false。当所有的数遍历完了，就return true。 ☆─────────────────────────────────────☆ Andier (La.is.la.bonita) 于 (Tue Aug 3 10:02:44 2010) 提到: 【在 wks 的大作中提到: 】 : 反例：6,3,7,5,9 : 开始： : upperBound = 9 : ................... 多谢。修改了一下。我觉得ok了，你再看看:) ☆─────────────────────────────────────☆ xiecaiji (wbc粉丝团----饼干---谁说装不像) 于 (Tue Aug 3 10:50:02 2010) 提到: 【在 SuK 的大作中提到: 】 : 想了2分钟，不一定好用哈，只是提供一种思路：反过来呢，从最后一个数开始，往前找，对于每一个数，如果前面有数大于他，设has_bigger=1，如果有数小于他，设has_smaller=1,如果遍历完整个数列不满足 has_bigger && has_smaller，那么对前一个数开始遍历，否则return false。当所有的数遍历完了，就return true。 : -- o(n2)了

[合集] 请教一道算法题