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

zltzlt

今天的题目：

数组中的两个数字如果前面一个数大于后面的一个数，则这两个数字组成一个逆序对。
也就是，如果 a[c] > a[d] 且 c < d，a[c] 和 a[d] 构成一个逆序对。

给定一个数组，求出这个数组中逆序对的总数。

示例 1：

输入：[2, 4, 1, 3, 5]
输出：3
解释：(2, 1)、(4, 1)、(4, 3) 是逆序对。

示例 2：

输入：[1, 2, 3, 4]
输出：0
解释：数组中没有逆序对。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Croper

2020-1-12 19:57:27

先写一个

1. def func304(l:list):
   
2.     l2=[]
   
3.     ret=0
   
4.     for i in l:
   
5.         p,q=0,len(l2)
   
6.         while (p<q):
   
7.             n=(p+q)//2
   
8.             if (l2[n]>i):
   
9.                 q=n
   
10.             else:
    
11.                 p=n+1
    
12.         ret+=len(l2)-p
    
13.         l2.insert(p,i)
    
14.     return ret
    

复制代码

跳转到最佳答案楼层

Croper

先写一个

1. def func304(l:list):
   
2.     l2=[]
   
3.     ret=0
   
4.     for i in l:
   
5.         p,q=0,len(l2)
   
6.         while (p<q):
   
7.             n=(p+q)//2
   
8.             if (l2[n]>i):
   
9.                 q=n
   
10.             else:
    
11.                 p=n+1
    
12.         ret+=len(l2)-p
    
13.         l2.insert(p,i)
    
14.     return ret
    

复制代码

阴阳神万物主

抢板凳！
我来一个好朴素的解法：

1. def solve(lst:'list of int')->int:
   
2.     res = 0
   
3.     le = len(lst)
   
4.     temp = [(lst[i],i)for i in range(le)]
   
5.     temp.sort(key=lambda x:x[0],reverse=True)
   
6.     for l in range(le):
   
7.         for r in range(l+1,le):
   
8.             ln,li = temp[l]
   
9.             rn,ri = temp[r]
   
10.             if ln>rn and li<ri:
    
11.                 res += 1
    
12.     return res
    
13. if __name__ == '__main__':
    
14.     print('示例1 输出：',solve([2,4,1,3,5]))
    
15.     print('示例2 输出：',solve([1,2,3,4]))
    

复制代码

lixiangyv

代码：

1. def f304(array):
   
2.     t=0
   
3.     for i in range(len(array)-1,0,-1):
   
4.         flag=False
   
5.         for j in range(i):
   
6.             if array[j]>array[j+1]:
   
7.                 array[j],array[j+1]=array[j+1],array[j]
   
8.                 t+=1
   
9.                 flag=True
   
10.         if not flag:
    
11.             break
    
12.     return t%(2*(10**5))

复制代码

不知道效率咋样……

zltzlt

lixiangyv 发表于 2020-1-12 20:34
代码：

不知道效率咋样……

超时

kinkon

凑个热闹

1. def f304(n):
   
2.     L, res = len(n), []
   
3.     for i in range(L-1):
   
4.         for j in range(i+1,L):
   
5.             if n[i] > n[j]:
   
6.                 res.append((n[i], n[j]))         
   
7.    
   
8. 
   
9.     return len(res)

复制代码

zltzlt

kinkon 发表于 2020-1-12 20:38
凑个热闹

超时

阴阳神万物主

代码已出：三楼

zltzlt

阴阳神万物主 发表于 2020-1-12 20:26
抢板凳！
我来一个好朴素的解法：

双重 for 循环，超时

lixiangyv

这个会不会超时呢？

1. def f304(num):
   
2.         length = len(num)
   
3.         result = []
   
4.         small_num = []
   
5.         for i in range(length):
   
6.                 if num[i] in small_num:
   
7.                         continue
   
8.                 else:
   
9.                         for j in range(i, length):
   
10.                                 if num[i] > num[j]:
    
11.                                         result.append((num[i], num[j]))
    
12.                                         small_num.append(num[j])

复制代码

zltzlt

lixiangyv 发表于 2020-1-12 20:44
这个会不会超时呢？

没有返回值。。

lixiangyv

zltzlt 发表于 2020-1-12 20:45
没有返回值。。

额......没拷贝过来

1. def f304(num):
   
2.         length = len(num)
   
3.         result = []
   
4.         small_num = []
   
5.         for i in range(length):
   
6.                 if num[i] in small_num:
   
7.                         continue
   
8.                 else:
   
9.                         for j in range(i, length):
   
10.                                 if num[i] > num[j]:
    
11.                                         result.append((num[i], num[j]))
    
12.                                         small_num.append(num[j])
    
13.                
    
14.         return len(result)

复制代码

zltzlt

lixiangyv 发表于 2020-1-12 20:48
额......没拷贝过来

答案不正确

zltzlt

lixiangyv 发表于 2020-1-12 20:48
额......没拷贝过来

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

lixiangyv

zltzlt 发表于 2020-1-12 20:50
答案不正确

这样应该可以了吧

1. def f304(num):
   
2.         length = len(num)
   
3.         result = []
   
4.         for i in range(length):
   
5.                 for j in range(i, length):
   
6.                                 if num[i] > num[j]:
   
7.                                         result.append((num[i], num[j]))
   
8.                
   
9.         return len(result)

复制代码

zltzlt

lixiangyv 发表于 2020-1-12 20:55
这样应该可以了吧

超时，并且超出内存限制

凌九霄

1. def func304(l: list):
   
2.     result = 0
   
3.     while l.__len__():
   
4.         t = l.pop(0)
   
5.         for i in l:
   
6.             if i < t:
   
7.                 result += 1
   
8.     return result

复制代码

下面的改进版这个虽然没有理想中的快，但是应该快非常多了

1. def func304(l: list):
   
2.     result = 0
   
3.     while l.__len__():
   
4.         t = l.pop(0)
   
5.         v = [x for x in l if x < t]
   
6.         result += v.__len__()
   
7.     return result

复制代码

zltzlt

凌九霄 发表于 2020-1-12 20:57

超时

kinkon

kinkon 发表于 2020-1-12 20:38
凑个热闹

应该又解错题了

nianyi

a=list(input())
b=[]
for i in a:
    b.append(int(i))
c=0
for i in range(len(b)):
    for j in range(i+1,len(b)):
        if b[i]>b[j]:
            c+=1
print(c)