[LeetCode] Challenge log 658

Posted on |
658. Find K Closest Elements

It has some problems with test cases so can’t get it ac. Whatever, I have the correct code anyway…

  1. Binary search to locate the position
  2. Create a len(k) sliding window start from the position, slide it left until the furthest distance starts to increase.

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

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

Example 2:

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

Note:

  1. The value k is positive and will always be smaller than the length of the sorted array.
  2. Length of the given array is positive and will not exceed 104
  3. Absolute value of elements in the array and x will not exceed 104
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def findClosestElements(self, arr, k, x):
        """
        :type arr: List[int]
        :type k: int
        :type x: int
        :rtype: List[int]
        """
        def bs(arr, x):
            low = 0
            high = len(arr) - 1
            while low < high:
                mid = (low + high) // 2
                if arr[mid] < x:
                    low = mid + 1
                else:
                    high = mid
            return low
        
        # slide window
        pivot = bs(arr, x)
        left = pivot
        right = left + k - 1
        if right >= len(arr):
            left = left - (right - (len(arr) - 1))
            right = len(arr) - 1 
        min_dis = max(abs(arr[left]-x), abs(arr[right] -x))
        
        while left >= 0 and right >= pivot - 1:
            cur_dis = max(abs(arr[left]-x), abs(arr[right] -x))
            # print(left, right, cur_dis)
            if cur_dis <= min_dis:
                min_dis = cur_dis
                left -= 1
                right -= 1
            else:
                break
        return arr[left + 1: right + 2]
0%