uva 1608 不无聊的序列
2024-10-20 05:37:09
uva 1608 不无聊的序列
紫书上有这样一道题：
如果一个序列的任意连续子序列中都至少有一个只出现一次的元素，则称这个序列时不无聊的。输入一个n个元素的序列，判断它是不是无聊的序列。n<=200000。
首先，在整个序列中找到只出现一次的元素ai。如果不能找到，那它就是无聊的。不然，就可以退出当前循环，递归判断[1, i-1]和[i+1, n]是不是无聊的序列。
然而怎么找ai很重要。如果从一头开始找，那么最差情况下的时间复杂度就是O(n^2)的。而如果从两头开始找，那么最差情况就变成了ai在中间，时间复杂度是O(nlogn)！这是因为在中间的找起来慢，分起来快，而在两端的找起来快，分起来慢。有些时候用好中途相遇法还是很重要的。
最新文章
- win8改win7笔记
- html5图像组合
- 流行ORM产品优缺点分析--EntityFramework、NHibernate、PetaPoco
- 未能加载文件或程序集“System.Data.SQLite”或它的一个依赖。试图加载格式不正确的程序
- N久没写过东西了..写个最近在研究的程序
- Ubuntu之MaxScale安装配置
- poj 1847 最短路简单题，dijkstra
- 洛谷P2737 [USACO4.1]麦香牛块Beef McNuggets
- JavaScript高级程序设计之window对象
- LInux下socket编程学习笔记
- 关于unity3d播放flash动画，使用插件uniswf
- jquery第三期：js与jquery对象转换
- MacOS 10.12 Sierra 安全性与隐私没有任何来源选项解决方法
- HttpClient实现HTTP文件通用下载类
- Pytorch基本变量类型FloatTensor与Variable
- leetcode44
- DRF序列化/反序列化
- LeetCode DB: Department Highest Salary
- [转]好文章：Android的AlertDialog详解
- 【bug记录】jpa 解决org.hibernate.lazyinitializationexception could not initialize proxy - no session