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

zltzlt

今天的题目：

给一个目标数 target，一个非负整数 k 和一个按照升序排列的数组 A。
在 A 中找与 target 最接近的 k 个整数。

返回这 k 个数并按照与 target 的接近程度从小到大排序。如果接近程度相等，那么小的数排在前面。

示例 1：

输入：A = [1, 2, 3], target = 2, k = 3
输出：[2, 1, 3]

示例 2：

输入：A = [1, 4, 6, 8], target = 3, k = 3
输出：[4, 1, 6]

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Croper

2020-1-6 20:20:57

1. def func_301(target,k,l):
   
2.     p,q=0,len(l)
   
3.     while (p<q):
   
4.         n=(p+q)//2
   
5.         if l[n]>=target:
   
6.             q=n
   
7.         else:
   
8.             p=n+1
   
9.     p-=1
   
10.     ret=[]
    
11.     for i in range(k):
    
12.         m=-1
    
13.         if p>=0:
    
14.             m=1
    
15.             n=abs(target-l[p])
    
16.         if q<len(l) and (m==-1 or n>abs(target-l[q])):
    
17.             m=2
    
18.         if (m==1):
    
19.             ret.append(l[p])
    
20.             p-=1
    
21.         elif (m==2):
    
22.             ret.append(l[q])
    
23.             q+=1
    
24.     return ret

复制代码

跳转到最佳答案楼层

Croper

1. def func_301(target,k,l):
   
2.     p,q=0,len(l)
   
3.     while (p<q):
   
4.         n=(p+q)//2
   
5.         if l[n]>=target:
   
6.             q=n
   
7.         else:
   
8.             p=n+1
   
9.     p-=1
   
10.     ret=[]
    
11.     for i in range(k):
    
12.         m=-1
    
13.         if p>=0:
    
14.             m=1
    
15.             n=abs(target-l[p])
    
16.         if q<len(l) and (m==-1 or n>abs(target-l[q])):
    
17.             m=2
    
18.         if (m==1):
    
19.             ret.append(l[p])
    
20.             p-=1
    
21.         elif (m==2):
    
22.             ret.append(l[q])
    
23.             q+=1
    
24.     return ret

复制代码

lixiangyv

我的答案：

1. def f301(A, target, k):
   
2.         if (not A) or (not target):
   
3.                 return []
   
4.        
   
5.         else:
   
6.                 result = []
   
7.                 differ = []
   
8.                 iv = []
   
9.                 for i in A:
   
10.                         if i == target:
    
11.                                 result.append(i)
    
12.                                 k -= 1
    
13.                         else:
    
14.                                 differ.append(abs(i - target))
    
15.                                 iv.append(i)
    
16. 
    
17.                 if len(result) < k:
    
18.                         for i in range(k):
    
19.                                 mind = min(differ)
    
20.                                 result.append(iv[differ.index(mind)])
    
21.                                 iv.pop(differ.index(mind))
    
22.                                 differ.remove(mind)
    
23. 
    
24.                 return result

复制代码

zltzlt

lixiangyv 发表于 2020-1-6 20:29
我的答案：

解答错误

输入：A = [1,2,4,5,6,7,8,10], target = 5, k = 0
输出：[5]
预期结果：[]

lixiangyv

zltzlt 发表于 2020-1-6 20:30
解答错误

输入：A = [1,2,4,5,6,7,8,10], target = 5, k = 0

额......，
这样可以了吧：

1. def f301(A, target, k):
   
2.         if (not A) or (not target) or (not k):
   
3.                 return []
   
4.        
   
5.         else:
   
6.                 result = []
   
7.                 differ = []
   
8.                 iv = []
   
9.                 for i in A:
   
10.                         if i == target:
    
11.                                 result.append(i)
    
12.                                 k -= 1
    
13.                         else:
    
14.                                 differ.append(abs(i - target))
    
15.                                 iv.append(i)
    
16. 
    
17.                 if len(result) < k:
    
18.                         for i in range(k):
    
19.                                 mind = min(differ)
    
20.                                 result.append(iv[differ.index(mind)])
    
21.                                 iv.pop(differ.index(mind))
    
22.                                 differ.remove(mind)
    
23. 
    
24.                 return result

复制代码

NAMELESSONE

1. def less(A:list,k:int,target:int):
   
2.         A.sort()
   
3.         B=[]
   
4.         A.sort(key=lambda x:abs(x-target),reverse=True)
   
5.         for i in range(0,k):
   
6.                 B.append(A.pop())
   
7.         return B

复制代码

zltzlt

NAMELESSONE 发表于 2020-1-6 21:07

解答错误

输入：A = [1,2,3], target = 2, k = 3
输出：[2, 3, 1]
预期结果：[2, 1, 3]

NAMELESSONE

zltzlt 发表于 2020-1-6 21:17
解答错误

输入：A = [1,2,3], target = 2, k = 3

1. def less(A:list,k:int,target:int):
   
2.         A.sort(reverse=True)
   
3.         B=[]
   
4.         A.sort(key=lambda x:abs(x-target),reverse=True)
   
5.         for i in range(0,k):
   
6.                 B.append(A.pop())
   
7.         return B

复制代码

NAMELESSONE

zltzlt 发表于 2020-1-6 21:17
解答错误

输入：A = [1,2,3], target = 2, k = 3

楼主，这个效率你是咋检查的

zltzlt

NAMELESSONE 发表于 2020-1-6 21:28
楼主，这个效率你是咋检查的

暂不透露

塔利班

1. def f301(A,target,k):
   
2.     if not A:
   
3.         return []
   
4.     l, r = 0, len(A) - 1
   
5.     while l + 1 < r:
   
6.         m = (l + r) // 2
   
7.         if A[m] > target:
   
8.             r = m
   
9.         else:
   
10.             l = m
    
11.    
    
12.     res = []
    
13. 
    
14.     for i in range(k):
    
15. 
    
16.         if l< 0:
    
17.             res.append(A[r])
    
18.             r += 1
    
19.         elif r > len(A) - 1:
    
20.             res.append(A[l])
    
21.             l -= 1
    
22.         else:
    
23.             if target - A[l] > A[r] - target:
    
24.                 res.append(A[r])
    
25.                 r += 1
    
26.             else:
    
27.                 res.append(A[l])
    
28.                 l -= 1
    
29.         
    
30.     return res

复制代码

logn+k

冬雪雪冬

1. def fun(A, target, k):
   
2.     A.sort(key = lambda x: abs(x - target))
   
3.     return A[: k]

复制代码

fan1993423

最开始的想法已经被冬雪大佬占用了，那久借用楼主的小技巧吧，现学现用

1. from bisect import bisect
   
2. def fun301(lst,target,k):
   
3.     if not len(lst):return 0
   
4.     result=[]
   
5.     for _ in range(k):
   
6.         index=bisect(lst,target)
   
7.         if abs(lst[index]-target)>abs(lst[index-1]-target):
   
8.             result.append(lst[index-1])
   
9.             lst.pop(index-1)
   
10.         else:
    
11.             result.append(lst[index]),lst.pop(index)
    
12.     return result
    

复制代码

kinkon

来个笨办法

1. def f301(A, target, k):
   
2.     A =sorted(set(A))
   
3.     res,res1 = [],[]
   
4.     if not A or not target or not k: return []
   
5.    
   
6.     elif target in A and k >= 1:
   
7.         res = [target]
   
8.         A.remove(target)
   
9.         for i in A[:k-1]:
   
10.             res.append(i)
    
11.     elif not target in A and k >= 1:
    
12.         for i in A:            
    
13.             res1.append(abs(target-i))
    
14.         p = res1.index(min(res1))
    
15.         res = [A[p]]
    
16.         del A[p]
    
17.         for i in A[:k-1]:
    
18.             res.append(i)
    
19.     return res

复制代码

TJBEST

采用二分查找来做的题，理论上时间log(n)+k

1. def fun301(A,target,k):
   
2.     def findleft(start,end):
   
3.         index = (start + end)//2
   
4.         if A[index] < target:
   
5.             if A[index + 1]>= target:
   
6.                 return index
   
7.             else:
   
8.                 return findleft(index,end)
   
9.         else:
   
10.             return findleft(start,index)
    
11.     def findright(start,end):
    
12.         index = (start + end + 1)//2
    
13.         if A[index] > target:
    
14.             if A[index - 1]<= target:
    
15.                 return index
    
16.             else:
    
17.                 return findright(start,index)
    
18.         else:
    
19.             return findright(index,end)         
    
20.               
    
21.         
    
22.     if k == 0:
    
23.         return []
    
24.     else:
    
25.         if target >= A[len(A) - 1]:
    
26.             return list(reversed(A))[0:k]
    
27.         elif target <= A[0]:
    
28.             return A[0:k]
    
29.         left = findleft(0,len(A))
    
30.         right = findright(0,len(A))
    
31.         if k <= right - left -1:
    
32.             return [target]*k
    
33.         else:
    
34.             res = []
    
35.             res.extend([target]*(right - left -1))
    
36.             count = k - (right - left -1)#>0
    
37.             lf = 0
    
38.             rt = 0
    
39.             index = 0
    
40.             while index < count:
    
41.                 if right + rt == len(A):
    
42.                     res.append(A[left - lf])
    
43.                     lf = lf + 1
    
44.                     index = index + 1
    
45.                 elif left - lf < 0:
    
46.                     res.append(A[right + rt])
    
47.                     rt = rt + 1
    
48.                     index = index + 1
    
49.                 else:
    
50.                     if abs(A[left - lf] - target) <= abs(A[right + rt] - target):
    
51.                         res.append(A[left - lf])
    
52.                         lf = lf + 1
    
53.                         index = index + 1
    
54.                     else:
    
55.                         res.append(A[right + rt])
    
56.                         rt = rt + 1
    
57.                         index = index + 1
    
58.             return res

复制代码

逄逄

1. def target_increasing(target, k, array):
   
2.     '''从升序数组array中找到与target最接近的k个数，按照接近程度输出，同程度按升序排列'''
   
3.     diff = {}
   
4.     for number in array:
   
5.         difference = abs(number-target)
   
6.         if difference in diff:
   
7.             diff[difference].append(number)
   
8.         else:
   
9.             diff[difference] = [number]
   
10. 
    
11.     keys = sorted(diff.keys())
    
12.     count = 0
    
13.     output = []
    
14.     for each_diff in keys:
    
15.         for each_num in diff[each_diff]:
    
16.             output.append(each_num)
    
17.             count += 1
    
18. 
    
19.             if count == k:
    
20.                 print(output)
    
21.                 return

复制代码

kinkon

zltzlt 发表于 2020-1-6 21:42
暂不透露

代码短的感觉输出是错的
A = [2,4,6,8,10,33,77,66,45,32], target = 12, k = 6

阴阳神万物主

我来晚了一步。

1. def solve(A:'list of int',target:int,k:int)->list:
   
2.     d = dict()
   
3.     #如果要返回的列表不能有重复的数字的话，把下一行前面的 '#' 符号删掉
   
4.     #A = set(A)
   
5.     for each in A:
   
6.         dis = abs(each - target)
   
7.         if dis in d:
   
8.             d[dis].append(each)
   
9.         else:
   
10.             d[dis] = [each]
    
11.     res = []
    
12.     for each in sorted(d):
    
13.         res += sorted(d[each])
    
14.         if len(res) >= k:
    
15.             break
    
16.     return res[:k]
    
17. if __name__ == '__main__':
    
18.     print('示例1 输出：',solve([1,2,3],2,3))
    
19.     print('示例2 输出：',solve([1,4,6,8],3,3))
    

复制代码

好像时间复杂度是 2n

776667

1. def fun301(A,target,k):
   
2.     B = [abs(i-target) for i in A]
   
3.     C = sorted(B)
   
4.     result = []
   
5.     while k:
   
6.         for j in range(len(A)):
   
7.             if abs(A[j]-target) == C[0]:
   
8.                 result.append(A[j])
   
9.                 k -= 1
   
10.                 C = C[1:]
    
11.                 A = A[:j] + A[j+1:]
    
12.                 break
    
13.     return result

复制代码

zltzlt

fan1993423 发表于 2020-1-7 09:54
最开始的想法已经被冬雪大佬占用了，那久借用楼主的小技巧吧，现学现用

IndexError: list index out of range