python | 算法練習(xí) 在排序數(shù)組中找最接近的K個(gè)數(shù)

分析：

首和尾兩個(gè)指針，左邊指針對(duì)應(yīng)的值與目標(biāo) target 的差，與右邊指針對(duì)應(yīng)的值與目標(biāo) target的差進(jìn)行比較

左邊的差<=右邊的差

則右邊指針向左移動(dòng)一個(gè)

反之：

左邊指針向右移動(dòng)一個(gè)

直到左指針到有指針的元素個(gè)數(shù) == k 的時(shí)候，說(shuō)明取到 k 個(gè)距離 target 最近的整數(shù)了

對(duì)A[left_index: right_index+1]中的元素，與目標(biāo) target的差值進(jìn)行升序排序

得到目標(biāo)列表

class Solution:
 ? ?"""
 ? ?@param A: an integer array
 ? ?@param target: An integer
 ? ?@param k: An integer
 ? ?@return: an integer array
 ? ?"""
 ? ?def kClosestNumbers(self, A, target, k):
 ? ? ? ?# write your code here
 ? ? ? ?left_index = 0
 ? ? ? ?right_index = len(A) - 1
 ? ? ? ?if k == 0:
 ? ? ? ? ? ?return []

? ? ? ?while left_index <= right_index:
? ? ? ? ? ?if right_index - left_index + 1 == k:

? ? ? ? ? ? ? ?result_list = [{"sub": abs(a-target), "value": a} for a in A[left_index:right_index+1]]
? ? ? ? ? ? ? ?sort_result_list = sorted(result_list, key=lambda result_list: result_list["sub"])
? ? ? ? ? ? ? ?return [res["value"] for res in sort_result_list]

? ? ? ? ? ?if right_index - left_index + 1 > k:
? ? ? ? ? ? ? ?left_close = abs(target - A[left_index])
? ? ? ? ? ? ? ?right_close = abs(A[right_index] - target)
? ? ? ? ? ? ? ?if left_close <= right_close:
? ? ? ? ? ? ? ? ? ?right_index -= 1
? ? ? ? ? ? ? ?if left_close > right_close:
? ? ? ? ? ? ? ? ? ?left_index += 1

補(bǔ)充：

對(duì)列表進(jìn)行按照元素字典的鍵進(jìn)行排序：

sorted(result_list,key=lambda result_list:result["key"])

取絕對(duì)值：

abs()