[LeetCode] 658. Find K Closest Elements 寻找K个最近元素

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 658. Find K Closest Elements 寻找K个最近元素,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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.html

Example 1:java

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

Example 2:python

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 

UPDATE (2017/9/19):
The arr parameter had been changed to an array of integers (instead of a list of integers). Please reload the code definition to get the latest changes.post

给一个有序数组和整数k, x,找出数组中离x最近的k个数。url

解法1: 因为数组有序,因此最后找到的k个元素也必定是有序的,其实就是返回了一个长度为k的子数组,至关于在长度为n的数组中去掉n-k个数字,并且去掉的顺序确定是从两头开始去,由于距离x最远的数字确定在首尾出现。每次比较首尾两个数字跟x的距离,将距离大的那个数字删除,直到剩余的数组长度为k为止。spa

解法2: 二分法。 每次比较的是mid位置和x的距离跟mid+k跟x的距离,以这二者的大小关系来肯定二分法折半的方向,最后找到最近距离子数组的起始位置。code

Java:htm

public List<Integer> findClosestElements(int[] A, int k, int x) {
        int left = 0, right = A.length - k;
        while (left < right) {
            int mid = (left + right) / 2;
            if (x - A[mid] > A[mid + k] - x)
                left = mid + 1;
            else
                right = mid;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i++) res.add(A[left + i]);
        return res;
    }  

Java:blog

public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
        int index = Collections.binarySearch(arr, x);
        if(index < 0) index = -(index + 1);
        int i = index - 1, j = index;                                    
        while(k-- > 0){
            if(i<0 || (j<arr.size() && Math.abs(arr.get(i) - x) > Math.abs(arr.get(j) - x) ))j++;
            else i--;
        }
        return arr.subList(i+1, j);
    } 

Java:

public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
    int lo = 0, hi = arr.size() - k;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (x - arr.get(mid) > arr.get(mid+k) - x)
            lo = mid + 1;
        else
            hi = mid;
    }
    return arr.subList(lo, lo + k);
}

Python:

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

Python:

import bisect

class Solution(object):
    def findClosestElements(self, arr, k, x):
        """
        :type arr: List[int]
        :type k: int
        :type x: int
        :rtype: List[int]
        """
        i = bisect.bisect_left(arr, x)
        left, right = i-1, i
        while k:
            if right >= len(arr) or \
               (left >= 0 and abs(arr[left]-x) <= abs(arr[right]-x)):
                left -= 1
            else:
                right += 1
            k -= 1
        return arr[left+1:right]

Python:  

def findClosestElements(self, arr, k, x):
        left = right = bisect.bisect_left(arr, x)
        while right - left < k:
            if left == 0: return arr[:k]
            if right == len(arr): return arr[-k:]
            if x - arr[left - 1] <= arr[right] - x: left -= 1
            else: right += 1
        return arr[left:right] 

C++:

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        vector<int> res = arr;
        while (res.size() > k) {
            int first  = 0, last = res.size() - 1;
            if (x - res.front() <= res.back() - x) {
                res.pop_back();
            } else {
                res.erase(res.begin());
            }
        }
        return res;
    }
};

C++:  

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0, right = arr.size() - k;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (x - arr[mid] > arr[mid + k] - x) left = mid + 1;
            else right = mid;
        }
        return vector<int>(arr.begin() + left, arr.begin() + left + k);
    }
};

C++:  

vector<int> findClosestElements(vector<int>& A, int k, int x) {
        int left = 0, right = A.size() - k;
        while (left < right) {
            int mid = (left + right) / 2;
            if (x - A[mid] > A[mid + k] - x)
                left = mid + 1;
            else
                right = mid;
        }
        return vector<int>(A.begin() + left, A.begin() + left + k);
    }

  

 

 

All LeetCode Questions List 题目汇总