動機

  1. bisect的index要處理好
  2. 就算是greedy，也要讓程式判斷再去長
  3. 你的sliding window不是我的sliding windows

Problem

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

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= k <= arr.length
  • 1 <= arr.length <= 104
  • arr is sorted in ascending order.
  • -104 <= arr[i], x <= 104

Sol

之前想說只要讓他一直先往左長，不夠再去右

但這樣就出事了，因為不一定保證大於右

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        i = bisect_left(arr,x)
        if i == len(arr): # 用bisect一定要處理這個case
            i -= 1
        if i-1 >=0 and arr[i] != x: # 小心負數index
            i = i-1 if abs(arr[i-1]-x) <= abs(arr[i]-x) else i

        a,b = i,i+1
        while b-a < k: # 讓程式判斷，不要自幹，除非很確定
            if 0 <= a and b < len(arr):
                if abs(arr[a-1]-x) <= abs(arr[b]-x):
                    a -= 1
                else:
                    b += 1
            elif 0 <= a:
                a -= 1
            else:
                b += 1
        return arr[a:b]