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

zltzlt

闲愚 发表于 2019-12-13 00:37

输入大数据超时

zltzlt

Croper 发表于 2019-12-13 01:05

恭喜通过！

执行用时：252 ms

zltzlt

sn8625 发表于 2019-12-13 01:33

输入大数据超时

zltzlt

hrp 发表于 2019-12-13 04:29

当 array 为空列表时报错

zltzlt

阴阳神万物主 发表于 2019-12-13 12:37
目前，我唯一好奇的是：
为什么
怎么突然来这么一个复数形式？

还是你观察得仔细啊……

不过，用双重 for 循环是会超时滴

zltzlt

fan1993423 发表于 2019-12-13 17:55

这是第 289 题。。。

Unicorn#

zltzlt 发表于 2019-12-13 19:31
当 array 为空列表时报错

1. def solve(array, queries):
   
2.     if not queries:
   
3.         return []
   
4.     array.sort()
   
5.     def count(num):
   
6.         i = 0
   
7.         for i in range(len(array)):
   
8.             if array[i] >= num:
   
9.                 break
   
10.         return i
    
11.     return list(map(count, queries))

复制代码

zltzlt

冬雪雪冬 发表于 2019-12-13 18:53

输入大数据会超时

zltzlt

Unicorn# 发表于 2019-12-13 19:43

输入大数据会超时

TJBEST

zltzlt 发表于 2019-12-13 19:33
当 array 为空列表时报错

需要对那个列表判断空格？

zltzlt

TJBEST 发表于 2019-12-13 19:55
需要对那个列表判断空格？

如果 array 为空时，返回 [0] * len(queries)。

TJBEST

zltzlt 发表于 2019-12-13 19:56
如果 array 为空时，返回 [0] * len(queries)。

1. def fun(array,queries):
   
2.     if array ==[]:
   
3.         teshu = []
   
4.         for eachTeshu in queries:
   
5.             teshu.append(0)
   
6.         return teshu
   
7.     givenList = sorted(array)
   
8.     checkList = sorted(set(queries))
   
9.     checkNumList = []
   
10.     for eachNum in checkList:
    
11.         if eachNum <= givenList[0]:
    
12.             checkNumList.append(0)
    
13.         elif eachNum > givenList[len(givenList)-1]:
    
14.             checkNumList.append(len(givenList))
    
15.         else:
    
16.             if checkNumList==[]:
    
17.                 indexA = 0
    
18.             elif checkNumList[len(checkNumList)-1]==0:
    
19.                 indexA = 0
    
20.             else:
    
21.                 indexA = checkNumList[len(checkNumList)-1]-1
    
22.                
    
23.             while True:
    
24.                 if givenList[indexA]<eachNum and givenList[indexA+1]>=eachNum:
    
25.                     break
    
26.                 else:
    
27.                     indexA = indexA + 1
    
28.             checkNumList.append(indexA+1)
    
29.     newMap = dict(zip(checkList,checkNumList))
    
30.     result = []
    
31.     for eachRe in queries:
    
32.          result.append(newMap[eachRe])
    
33.     return result
    

复制代码

hrp

zltzlt 发表于 2019-12-13 19:37
当 array 为空列表时报错

1. def func289(array, queries):
   
2.     result = []
   
3.     if not array:
   
4.         result.append(0)
   
5.         return result * len(queries)
   
6.     array.sort()
   
7.     for i in queries:
   
8.         for j in array:
   
9.             if j >= i:
   
10.                 break
    
11.         result.append(array.index(j))
    
12.     return result

复制代码

danteer

我呢我呢

zltzlt

hrp 发表于 2019-12-13 20:29

如果 array 为空时，返回的是 [0] * len(queries)。

hrp

zltzlt 发表于 2019-12-13 21:10
如果 array 为空时，返回的是 [0] * len(queries)。

看错了

阴阳神万物主

zltzlt 发表于 2019-12-13 19:40
还是你观察得仔细啊……

不过，用双重 for 循环是会超时滴

是一切双重for都超时吗？
我来一个玩生成器的看看。

1. def solve(array:'整数数组',queries:'查询列表')->'最终列表':
   
2.     def query():
   
3.         nonlocal array
   
4.         array.sort(reverse=True)
   
5.         le = len(array)
   
6.         for each in queries:
   
7.             for i in range(le):
   
8.                 if array[i] < each:
   
9.                     yield le-i
   
10.                     break
    
11.             else:
    
12.                 yield 0
    
13.     return list(query())
    
14. 
    
15. if __name__ == '__main__':
    
16.     print('示例1 输出：',solve([1,2,7,8,5],[1,8,5]))
    
17.     print('示例2 输出：',solve([3,4,5,8],[2,4]))
    

复制代码

我再来个，array 越来越短的看看，似乎时间复杂度为 O(2n)

1. def solve(array:'整数数组',queries:'查询列表')->'最终列表':
   
2.     le = len(queries)
   
3.     res = [0]*le
   
4.     array.sort(reverse=True)
   
5.     query = sorted(zip(queries,range(le)),key=lambda x:x[0],reverse=True)
   
6.     la = len(array)
   
7.     for each in query:
   
8.         for i in range(la):
   
9.             if each[0] > array[i]:
   
10.                 break
    
11.         else:
    
12.             i += 1
    
13.         array = array[i:]
    
14.         la = len(array)
    
15.         res[each[1]] = la
    
16.     return res
    
17. if __name__ == '__main__':
    
18.     print('示例1 输出：',solve([1,2,7,8,5],[1,8,5]))
    
19.     print('示例2 输出：',solve([3,4,5,8],[2,4]))
    
20. 
    

复制代码

Croper

没看懂。。

1. def fun(array,queries):
   
2.     if array ==[]:
   
3.         teshu = []
   
4.         for eachTeshu in queries:
   
5.             teshu.append(0)
   
6.         return teshu
   
7.     givenList = sorted(array)
   
8.     checkList = sorted(set(queries))
   
9.     checkNumList = []
   
10.     for eachNum in checkList:
    
11.         if eachNum <= givenList[0]:
    
12.             checkNumList.append(0)
    
13.         elif eachNum > givenList[len(givenList)-1]:
    
14.             checkNumList.append(len(givenList))
    
15.         else:
    
16.             if checkNumList==[]:
    
17.                 indexA = 0
    
18.             elif checkNumList[len(checkNumList)-1]==0:
    
19.                 indexA = 0
    
20.             else:
    
21.                 indexA = checkNumList[len(checkNumList)-1]-1
    
22.                
    
23.             while True:
    
24.                 if givenList[indexA]<eachNum and givenList[indexA+1]>=eachNum:
    
25.                     break
    
26.                 else:
    
27.                     indexA = indexA + 1
    
28.             checkNumList.append(indexA+1)
    
29.     newMap = dict(zip(checkList,checkNumList))
    
30.     result = []
    
31.     for eachRe in queries:
    
32.          result.append(newMap[eachRe])
    
33.     return result

复制代码

1. def querylist(array,queries):
   
2.     temp=list(range(len(queries)))
   
3. 
   
4.     array.sort()
   
5.     temp.sort(key=lambda i:queries[i])
   
6. 
   
7.     k=0
   
8.     for i in temp:
   
9.         while (k<len(array) and array[k]<queries[i]):
   
10.             k+=1
    
11.         queries[i]=k
    
12.     return queries

复制代码

为什么答案1能比答案2快了，思路几乎都是一样的，双排序，然后用类似双指针的解法，考虑排序，时间复杂度都是O[M*logM+N*logN+M+N],
细节上看，答案1的执行步骤也比答案2多啊。。

TJBEST

Croper 发表于 2019-12-13 22:20
没看懂。。

我看思路确实类似，可能是我对边界的讨论比较细，从而简单一些，也希望有大神解释一下。

fan1993423

不好意思，粘贴错题了，但是麻烦楼主把题描述详细点好嘛？我也是看到答友才知道array可以为空列表。不说的话我又是默认array不为空的情况下写代码

1. def fun289(array:list,query:list):
   
2.     if not len(array):
   
3.         return [0]*len(query)
   
4.     result=[]
   
5.     for i in query:
   
6.         combination=sorted(array+[i])
   
7.         result.append(combination.index(i))
   
8.     return result
   

复制代码