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

zltzlt

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

会超时

多洛克沙拉姆

x= input("请输入一组数字：")
list1 = x.split(",")
n= len(list1)
count = 0
for m in range(0, n):
    for i in range(m+1, n):
        if list1[m] > list1[i]:
            count = count + 1
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

def func304(l):
    res = 0
    while l:
        s = l.index(max(l))
        e = l.index(l[-1])
        res += (e - s)
        l.pop(s)
    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）

def func304(l:list):
    l2=[]
    map={}
    for i in l:
        exist=False
        p,q=0,len(l2)
        while (p<q):
            n=(p+q)//2
            if (i==l2[n]):
                exist=True
                map[i]=n
                break
            if (l2[n]<i):
                q=n
            else:
                p=n+1
        if (not exist):
            l2.insert(p,i)
            map[i]=p
    ret=0
    for n in map.values():
        ret+=n
    return ret

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

阴阳神万物主

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

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

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

阴阳神万物主

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对

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

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