鱼C论坛

 找回密码
 立即注册
查看: 2816|回复: 3

[技术交流] 题目:判读是不是等差数列

[复制链接]
发表于 2017-7-4 17:57:45 | 显示全部楼层 |阅读模式
10鱼币
背景:题目来自知乎,偶然看到,所以来分享一下。自己虽然也写了一个,但是不知道算不算符号题意,所以copy过来看看各位的妙招!
来源https://zhuanlan.zhihu.com/p/23134333

Python 判读是不是等差数列,要求算法时间复杂度为O(NlogN)

不能用sort或sorted

问题: 判断等差数列

描述: 输入一个整数N,然后输入N个整数。判断这N个整数是否可以构建一个等差数列。(0<n<1000)

输入: 第一行为一个整数N,第二行为N个整数。

输出: 可以构成等差数列输出True,否则输出False。

示例:

(1)input: 10

5 3 2 1 7 6 4 8 10 9

output: True

(2)input: 5

4 6 3 2 7

output: False

提示:需要注意输入的数可以没有大小顺序。

这个题目来自一个C语言提问者的提问,觉得对初学者有益,就转载过来。

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-7-4 20:19:45 | 显示全部楼层
  1. >>> def is_AP(s:str)->bool:
  2.         sequ = tuple(map(int,s.split()))
  3.         ln = len(sequ)
  4.         n,m = min(sequ),max(sequ)
  5.         dif = (m-n)//(ln-1)
  6.         rng = range(n, m+dif, dif)
  7.         if len(rng)!=ln:
  8.                 return False
  9.         for i in sequ:
  10.                 if i not in rng:
  11.                         return False
  12.         return True

  13. >>> is_AP('4 6 3 2 7')
  14. False
  15. >>> is_AP('5 3 2 1 7 6 4 8 10 9')
  16. True
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2017-7-4 20:30:45 | 显示全部楼层

前面的部分跟你这个一样
我后面的核对比较部分没有用循环,而是用的set(),效果一样吧
只是不知道这种方式符不符合题目中时间复杂度
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-7-4 20:40:34 | 显示全部楼层
range 的 in 操作是O(1)
for 循环是 O(n)
基本上差不多吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 20:28

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表