Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.
An integer a is closer to x than an integer b if:
|a - x| < |b - x|, or
|a - x| == |b - x| and a < b
#이차원배열 #큐 #정렬
n-x의 값을 idx와 함께 이차원배열의 형태(queue)로 저장한 뒤, n-x의 값이 작은 순서대로 k개를 뽑아 리턴한다. 인덱스 순서는 정렬되어야 하므로 마지막에 sort한다.
처음에는 포인터 두 개를 사용해 while문으로 시도했으나, 여러 예외사항이 있어 알고리즘을 수정했다.
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
arr1 = [[abs(n-x),i] for i,n in enumerate(arr)] # arr에서 n-x값을 따로 빼내 저장한다.
arr1.sort(key = lambda x:x[0]) # 이차원배열을 n-x 순서대로 정렬한다.
return sorted([arr[arr1[i][1]] for i in range(k)]) # k개만큼 꺼내어 정렬한다.
Runtime: 472 ms, faster than 61.64% of Python3 online submissions for Find K Closest Elements.
Memory Usage: 16.7 MB, less than 5.36% of Python3 online submissions for Find K Closest Elements.