[Leetcode] 658. Find K Closest Elements

문제

 

https://leetcode.com/problems/find-k-closest-elements/description/

Find K Closest Elements - LeetCode

 

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.

 

정렬된 정수 배열 arr이 주어지고 정수 k, x가 주어질 때, 정수 x에서 가장 가까운 원소를 k개만큼 배열에 담아 오름차순으로 정렬하여 반환한다.

 

An integer a is closer to x than an integer b if:

• |a - x| < |b - x|, or
• |a - x| == |b - x| and a < b

 

Example 1:

Input	Output
arr = [1,2,3,4,5], k = 4, x = 3	[1,2,3,4]

Example 2:

Input	Output
arr = [1,2,3,4,5], k = 4, x = -1	[1,2,3,4]

 

문제풀이 코드

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        left, right = 0, len(arr) - k
        while left < right:
            mid = (left + right) // 2
            if x - arr[mid] > arr[mid + k] - x:
                left = mid + 1
            else:
                right = mid
        return arr[left:left + k]

투 포인터 방식으로 문제를 접근하였다

1. left = 0, right = 배열의 길이 - k로 두개의 포인터를 만들어준다

2. 두개의 포인터의 mid를 구한다.

3. x - arr[mid]와 arr[mid + k]값을 비교한다.

4. x - arr[mid]이 arr[mid + k]보다 크면 left = mid + 1

5. x - arr[mid]이 arr[mid + k]보다 작으면 right = mid

6. left 와 right가 같으면 루프를 종료하고 arr[left:left+k]를 리턴해준다.