[已解决]Python：每日一题 304

zltzlt

nianyi 发表于 2020-1-12 21:05
a=list(input())
b=[]
for i in a:

会超时

多洛克沙拉姆

1. x= input("请输入一组数字：")
   
2. list1 = x.split(",")
   
3. n= len(list1)
   
4. count = 0
   
5. for m in range(0, n):
   
6.     for i in range(m+1, n):
   
7.         if list1[m] > list1[i]:
   
8.             count = count + 1
   
9. print(count)

复制代码

凌九霄

zltzlt 发表于 2020-1-12 20:57
超时

说个数量级，也好改进自行测试下

zltzlt

凌九霄 发表于 2020-1-12 21:15
说个数量级，也好改进自行测试下

输入长度超过 10000 的数组超时

zltzlt

多洛克沙拉姆 发表于 2020-1-12 21:12

会超时

凌九霄

zltzlt 发表于 2020-1-12 21:16
输入长度超过 10000 的数组超时

改了个版本，应该快很多了

zltzlt

凌九霄 发表于 2020-1-12 21:41
https://fishc.com.cn/forum.php?mod=redirect&goto=findpost&ptid=153848&pid=4275578

同样会超时

hrp

1. def func304(l):
   
2.     res = 0
   
3.     while l:
   
4.         s = l.index(max(l))
   
5.         e = l.index(l[-1])
   
6.         res += (e - s)
   
7.         l.pop(s)
   
8.     return res

复制代码

zltzlt

hrp 发表于 2020-1-12 21:51

解答错误

输入：[4,4,2]
输出：3
预期结果：2

hrp

zltzlt 发表于 2020-1-12 21:53
解答错误

输入：[4,4,2]

想错了，还有重复数字

凌九霄

zltzlt 发表于 2020-1-12 21:45
同样会超时

看了下，10000的数量我测试不到3s，但100000跑了4分多，大部分时间耗在生成器上，如何能减少排序是关键

fan1993423

Croper 发表于 2020-1-12 19:57
先写一个

对于[2,4,1,1,5]，要求不计算重复的逆序对，该怎么弄

Croper

fan1993423 发表于 2020-1-12 22:08
对于[2,4,1,1,5]，要求不计算重复的逆序对，该怎么弄

不重复的逆序对？。。那你得先给个定义啊，什么叫做重复的，
。。比如[5,5,1,1,5,1,5,1]这种应该算有几个逆序对？

fan1993423

Croper 发表于 2020-1-12 22:20
不重复的逆序对？。。那你得先给个定义啊，什么叫做重复的，
。。比如[5,5,1,1,5,1,5,1]这种应该算有几 ...

一对 就是（5,1）

Croper

fan1993423 发表于 2020-1-12 23:00
一对 就是（5,1）

1. def func304(l:list):
   
2.     l2=[]
   
3.     map={}
   
4.     for i in l:
   
5.         exist=False
   
6.         p,q=0,len(l2)
   
7.         while (p<q):
   
8.             n=(p+q)//2
   
9.             if (i==l2[n]):
   
10.                 exist=True
    
11.                 map[i]=n
    
12.                 break
    
13.             if (l2[n]<i):
    
14.                 q=n
    
15.             else:
    
16.                 p=n+1
    
17.         if (not exist):
    
18.             l2.insert(p,i)
    
19.             map[i]=p
    
20.     ret=0
    
21.     for n in map.values():
    
22.         ret+=n
    
23.     return ret
    

复制代码

插入以第一个为准，计算以最后一个为准

阴阳神万物主

zltzlt 发表于 2020-1-12 20:44
双重 for 循环，超时

看了看别人的出错数据，感觉这回稳

1. def solve2(lst:'list of int')->int:
   
2.     res = 0
   
3.     temp = sorted(lst)
   
4.     for each in lst:
   
5.         if each in temp:
   
6.             res += temp.index(each)
   
7.             temp.remove(each)
   
8.     return res
   
9. if __name__ == '__main__':
   
10.     print('示例1 输出：',solve2([2,4,1,3,5]))
    
11.     print('示例2 输出：',solve2([1,2,3,4]))
    
12. 
    

复制代码

阴阳神万物主

fan1993423 发表于 2020-1-12 23:00
一对 就是（5,1）

我这个也行点击查看

Croper

阴阳神万物主 发表于 2020-1-12 23:46
我这个也行点击查看

输入[2,4,2],req设为False后结果是0对，预期结果是1对

阴阳神万物主

Croper 发表于 2020-1-12 23:55
输入[2,4,2],req设为False后结果是0对，预期结果是1对

哦豁

阴阳神万物主

Croper 发表于 2020-1-12 23:55
输入[2,4,2],req设为False后结果是0对，预期结果是1对

这样还有不对的吗，我这小脑瓜还是太嫩了

1. def solve2(lst:'list of int',rep=False)->int:
   
2.     res = 0
   
3.     temp = sorted(lst) if rep else sorted(set(lst))
   
4.     for each in lst:
   
5.         if each in temp[1:]:
   
6.             res += temp.index(each)
   
7.             temp.remove(each)
   
8.     return res

复制代码