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

zltzlt

Stubborn 发表于 2020-1-13 00:37
考虑下并归

解答错误

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

zltzlt

Unicorn# 发表于 2020-1-13 00:48
来了
尝试归并

解答错误

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

zltzlt

kinkon 发表于 2020-1-13 16:30
用迭代速度还可以吧

一样会超时

zltzlt

记忆的欠片 发表于 2020-1-13 19:54
def counter(arry):
    count = 0
    for i in arry:

解答错误

输入：[2,3,1,55,6,4,7,3,0]
输出：19
预期结果：18

阴阳神万物主

zltzlt 发表于 2020-1-15 07:48
还是会超时，原因在于 temp.index(each)

看来是时候去看效率革命了。（思考状）
不对，是奇技淫巧？

manmanpython

1. def solve2(array):
   
2.         """
   
3.         """
   
4.         array = list(enumerate(array))
   
5.         sorted_array = sorted(array, key=lambda x: x[1])
   
6.         count = 0
   
7.         for index, value in enumerate(sorted_array):
   
8.                 count += value[0] - index if (value[0] - index) > 0 else 0
   
9.         return count

复制代码

findland

1. def f304(s):
   
2.     count=0
   
3.     for i in range(len(s)):
   
4.         for j in  range(i+1,len(s)):
   
5.             if s[i]>s[j]:
   
6.                 count+=1
   
7.     return count

复制代码

一个账号

zltzlt 发表于 2020-1-12 20:56
超时，并且超出内存限制

你怎么知道超时并且超出内存限制？

wanting-for

1. def solve_304(A):
   
2.     B , count= A.copy(),0
   
3.     A.sort()
   
4.     for i in range(len(B)):
   
5.         if B[i]> A[i]:
   
6.             count+=A.index(B[i])-B.index(B[i])
   
7.     return count
   
8. if __name__ == "__main__":
   
9.     print('示例一:',solve_304([2, 4, 1, 3, 5]))
   
10.     print('示例二:',solve_304([1, 2, 3, 4]))

复制代码

如果没有问题的话，我感觉我的代码很漂亮！

wanting-for

版主可否帮忙测试一下代码的运行效率！谢谢大佬！！！@zltzlt

zltzlt

wanting-for 发表于 2020-1-18 13:49
如果没有问题的话，我感觉我的代码很漂亮！

解答错误

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

wanting-for

zltzlt 发表于 2020-1-18 13:55
解答错误

输入：[4, 4, 2]

1. def solve_304(A):
   
2.     B , count= A.copy(),0
   
3.     A.sort()
   
4.     for i in range(len(B)):
   
5.         if B[i]>= A[i]:
   
6.             count+=A.index(B[i])-B.index(B[i])
   
7.     return count
   
8. if __name__ == "__main__":
   
9.     print('示例二:',solve_304([4,4,2]))
   
10.     print('示例一:',solve_304([2, 4, 1, 3, 5]))
    
11.     print('示例二:',solve_304([1,2,3,4]))

复制代码

现在应该ok了，因该是>=

zltzlt

wanting-for 发表于 2020-1-18 14:01
现在应该ok了，因该是>=

解答错误

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

wanting-for

zltzlt 发表于 2020-1-18 14:03
解答错误

输入：[4, 3, 2, 1]

1. def mp_sort(A):
   
2.     count  = 0
   
3.     for i in range(len(A)):
   
4.         for j in range(len(A)-i-1):
   
5.             if A[j] > A[j+1]:
   
6.                 A[j+1], A[j]= A[j], A[j+1]
   
7.                 count +=1
   
8.     print(count)
   
9. mp_sort([4,3,2,1])

复制代码

总算找到了这个问题的精髓，就是排序，然后计算交换次数
交换次数就是这个逆序的个数

zltzlt

wanting-for 发表于 2020-1-18 14:18
总算找到了这个问题的精髓，就是排序，然后计算交换次数
交换次数就是这个逆序的个数{:5_109 ...

嗯，会超时

wanting-for

zltzlt 发表于 2020-1-18 14:20
嗯，会超时

冒泡排序，双层循环，n^2,效率偏低，换一下排序算法应该会好一些！

newbison

估计超时了~~~~

1. def func304(arr):
   
2. #如果 a[c] > a[d] 且 c < d，a[c] 和 a[d] 构成一个逆序对。给定一个数组，求出这个数组中逆序对的总数。''
   
3. 
   
4.     res = 0
   
5.     for i in range(0, len(arr)):
   
6.         for j in range(i+1, len(arr)):
   
7.             if arr[j] < arr[i]:
   
8.                 res += 1
   
9. 
   
10.     return res
    
11. 
    
12. if __name__ == '__main__':
    
13.     print('示例1 输出：',func304([2,4,1,3,5]))
    
14.     print('示例2 输出：',func304([4, 3, 2, 1]))

复制代码

ouyunfu

1. def f304(l:list)->int:
   
2.     count=0
   
3.     for i in range(len(l)-1):
   
4.         for j in range(i,len(l)):
   
5.             if l[i]>l[j]:
   
6.                 count+=1               
   
7.     return count
   
8. 
   
9. print(f304([2, 4, 1, 3, 5]))
   
10. print(f304([1, 2, 3, 4]))

复制代码