Leetcode - Find K Closest Elements

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

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:

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

Example 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 10⁴
3. Absolute value of elements in the array and x will not exceed 10⁴

func findClosestElements(arr []int, k int, x int) []int {
    if k == len(arr) {
        return arr
    }
    left := 0
    right := len(arr)-1
    var mid int
    for left <= right {
        mid = left + (right - left)/2
        if arr[mid] == x {
            right = mid
            break
        }
        if arr[mid] > x {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    left = right
    right++
    for k > 0 {
        if right >= len(arr) || (left >= 0 && x - arr[left] <= arr[right] - x) {
            left--
        } else {
            right++
        }
        k--
    }
    
    return arr[left+1:right]
}

• 相关文章
• 全局相关文章