自定义排序，二分查找（upper_bound / lower_bound + 双指针 / 直接找左边界）2 算法 4 解法，slice / array_slice / subList / Arrays.copyOfRange / GetRange / memcpy 截取列表，传递函数，求解《658. 找到 K 个最接近的元素》
例题
658. 找到 K 个最接近的元素
给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b
示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]
示例 2：
输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]
提示：
1 <= k <= arr.length
1 <= arr.length <= 104
arr 按 升序 排列
-104 <= arr[i], x <= 104
答案
排序 · 自定义排序 · 升序
var findClosestElements = function(arr, k, x) {
return arr.sort((a, b) => Math.abs(a - x) - Math.abs(b - x)).slice(0, k).sort((a, b) => a - b)
};function findClosestElements(arr: number[], k: number, x: number): number[] {
return arr.sort((a, b) => Math.abs(a - x) - Math.abs(b - x)).slice(0, k).sort((a, b) => a - b)
};func findClosestElements(arr []int, k int, x int) []int {
sort.SliceStable(arr, func(i, j int) bool {
return math.Abs(float64(arr[i] - x)) < math.Abs(float64(arr[j] - x))
})
ans := arr[:k]
sort.Ints(ans)
return ans
}class Solution {
function findClosestElements($arr, $k, $x) {
usort($arr, function($a, $b) use($x) {
$ax = abs($a - $x);
$bx = abs($b - $x);
return $ax > $bx;
});
$ans = array_slice($arr, 0, $k);
sort($ans, SORT_NUMERIC);
return $ans;
}
}class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
return sorted(sorted(arr, key = lambda v: abs(v - x))[:k])class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
List<Integer> ar = Arrays.stream(arr).boxed().collect(Collectors.toList());
Collections.sort(ar, (a, b) -> Math.abs(x - a) - Math.abs(x - b));
List<Integer> ans = ar.subList(0, k);
Collections.sort(ans);
return ans;
}
}public class Solution { // 截取数组
public IList<int> FindClosestElements(int[] arr, int k, int x) {
Array.Sort(arr, (a, b) => {
int t = Math.Abs(a - x) - Math.Abs(b - x);
if (t == 0) return a - b;
return t;
});
int[] ans = arr.Take(k).ToArray();
Array.Sort(ans);
return ans.ToList();
}
}public class Solution { // 截取列表 列表排序
public IList<int> FindClosestElements(int[] arr, int k, int x) {
Array.Sort(arr, (a, b) => {
int t = Math.Abs(a - x) - Math.Abs(b - x);
if (t == 0) return a - b;
return t;
});
List<int> ans = arr.ToList().GetRange(0, k);
ans.Sort();
return ans;
}
}int g_x;
static inline int cmpArr (const void *pa, const void *pb){
int a = *(int*)pa, b = *(int*)pb;
return abs(a - g_x) - abs(b - g_x);
}
static inline int cmpAns (const void *pa, const void *pb){
return *(int*)pa - *(int*)pb;
}
int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize){
g_x = x;
qsort(arr, arrSize, sizeof(int), cmpArr);
int* ans = malloc(sizeof(int) * k);
memcpy(ans, arr, sizeof(int) * k);
qsort(ans, k, sizeof(int), cmpAns);
*returnSize = k;
return ans;
}class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
sort(arr.begin(), arr.end(), [x](int a, int b) -> bool {
int ax = abs(a - x), bx = abs(b - x);
if (ax == bx) return a < b;
return abs(a - x) < abs(b - x);
});
vector<int> ans = vector<int>(arr.begin(), arr.begin() + k);
sort(ans.begin(), ans.end());
return ans;
}
};二分查找 （upper_bound 实现） · 双指针
var findClosestElements = function(arr, k, x) {
const n = arr.length
let l = upper_bound(arr, x) - 1, r = l + 1
while (r - l <= k) {
r >= n || l >= 0 && x - arr[l] <= arr[r] - x ? l-- : r++
}
return arr.slice(l + 1, r)
};
const upper_bound = (nums, num) => {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >>> 1
if (nums[m] > num) r = m - 1
else l = m + 1
}
return l
}func findClosestElements(arr []int, k int, x int) []int {
n := len(arr)
l := sort.Search(n, func(i int) bool {
return arr[i] > x
}) - 1
r := l + 1
for r - l <= k {
if (r >= n || l >= 0 && x - arr[l] <= arr[r] - x) {
l--
} else {
r++
}
}
return arr[l + 1: r]
}class Solution {
function findClosestElements($arr, $k, $x) {
$n = count($arr);
$l = $this->upper_bound($arr, $x) - 1;
$r = $r + 1;
while ($r - $l <= $k) {
$r >= $n || $l >= 0 && $x - $arr[$l] <= $arr[$r] - $x ? $l-- : $r++;
}
return array_slice($arr, $l + 1, $k);
}
function upper_bound($nums, $num) {
$l = 0;
$r = count($nums) - 1;
while ($l <= $r) {
$m = $l + $r >> 1;
if ($nums[$m] > $num) $r = $m - 1;
else $l = $m + 1;
}
return $l;
}
}class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
n, r = len(arr), bisect_left(arr, x)
l = r - 1
while r - l <= k:
if r >= n or l >= 0 and x - arr[l] <= arr[r] - x: l -= 1
else: r += 1
return arr[l + 1:r]class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int l = upper_bound(arr, x) - 1, r = l + 1, n = arr.length;
while (r - l <= k) {
if (r >= n || l >= 0 && x - arr[l] <= arr[r] - x) l--;
else r++;
}
return Arrays.stream(Arrays.copyOfRange(arr, l + 1, r)).boxed().collect(Collectors.toList());
}
private int upper_bound(int[] nums, int num) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int m = l + r >> 1;
if (nums[m] > num) r = m - 1;
else l = m + 1;
}
return l;
}
}public class Solution {
public IList<int> FindClosestElements(int[] arr, int k, int x) {
int l = upper_bound(arr, x) - 1, r = l + 1, n = arr.Length;
while (r - l <= k) {
if (r >= n || l >= 0 && x - arr[l] <= arr[r] - x) l--;
else r++;
}
return arr.ToList().GetRange(l + 1, k);
}
private int upper_bound(int[] nums, int num) {
int l = 0, r = nums.Length - 1;
while (l <= r) {
int m = l + r >> 1;
if (nums[m] > num) r = m - 1;
else l = m + 1;
}
return l;
}
}int upper_bound(int* nums, int numsSize, int num) {
int l = 0, r = numsSize - 1;
while (l <= r) {
int m = l + r >> 1;
if (nums[m] > num) r = m - 1;
else l = m + 1;
}
return l;
}
int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize){
int l = upper_bound(arr, arrSize, x) - 1, r = l + 1;
while (r - l <= k) {
r >= arrSize || l >= 0 && x - arr[l] <= arr[r] - x ? l-- : r++;
}
int* ans = malloc(sizeof(int) * k);
memcpy(ans, arr + l + 1, sizeof(int) *k);
*returnSize = k;
return ans;
}class Solution { // 自行实现 lower_bound
private:
int upper_bound(vector<int>& nums, int num) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int m = (l + r) >> 1;
if (nums[m] > num) r = m - 1;
else l = m + 1;
}
return l;
}
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int l = upper_bound(arr, x) - 1, r = l + 1, n = arr.size();
while (r - l <= k) {
r >= n || l >= 0 && x - arr[l] <= arr[r] - x ? l-- : r++;
}
return vector<int>(arr.begin() + l + 1, arr.begin() + r);
}
};class Solution { // 使用 #include <algorithm>
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int l = upper_bound(arr.begin(), arr.end(), x) - arr.begin() - 1, r = l + 1, n = arr.size();
while (r - l <= k) {
r >= n || l >= 0 && x - arr[l] <= arr[r] - x ? l-- : r++;
}
return vector<int>(arr.begin() + l + 1, arr.begin() + r);
}
};二分查找 (lower_bound 实现) · 双指针
function findClosestElements(arr: number[], k: number, x: number): number[] { // lower_bound 实现
const n = arr.length
let r = lower_bound(arr, x), l = r - 1
while (r - l <= k) {
r >= n || l >= 0 && x - arr[l] <= arr[r] - x ? l-- : r++
}
return arr.slice(l + 1, r)
};
const lower_bound = (nums: number[], num: number): number => {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >>> 1
if (nums[m] >= num) r = m - 1
else l = m + 1
}
return l
}func findClosestElements(arr []int, k int, x int) []int {
n := len(arr)
r := sort.Search(n, func(i int) bool {
return arr[i] >= x
})
l := r - 1
for r - l <= k {
if (r >= n || l >= 0 && x - arr[l] <= arr[r] - x) {
l--
} else {
r++
}
}
return arr[l + 1: r]
}class Solution {
function findClosestElements($arr, $k, $x) {
$n = count($arr);
$r = $this->lower_bound($arr, $x);
$l = $r - 1;
while ($r - $l <= $k) {
$r >= $n || $l >= 0 && $x - $arr[$l] <= $arr[$r] - $x ? $l-- : $r++;
}
return array_slice($arr, $l + 1, $k);
}
function lower_bound($nums, $num) {
$l = 0;
$r = count($nums) - 1;
while ($l <= $r) {
$m = $l + $r >> 1;
if ($nums[$m] >= $num) $r = $m - 1;
else $l = $m + 1;
}
return $l;
}
}class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
n, l = len(arr), bisect_right(arr, x) - 1
r = l + 1
while r - l <= k:
if r >= n or l >= 0 and x - arr[l] <= arr[r] - x: l -= 1
else: r += 1
return arr[l + 1:r]class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int r = lower_bound(arr, x), l = r - 1, n = arr.length;
while (r - l <= k) {
if (r >= n || l >= 0 && x - arr[l] <= arr[r] - x) l--;
else r++;
}
return Arrays.stream(Arrays.copyOfRange(arr, l + 1, r)).boxed().collect(Collectors.toList());
}
private int lower_bound(int[] nums, int num) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int m = l + r >> 1;
if (nums[m] >= num) r = m - 1;
else l = m + 1;
}
return l;
}
}public class Solution {
public IList<int> FindClosestElements(int[] arr, int k, int x) {
int r = lower_bound(arr, x), l = r - 1, n = arr.Length;
while (r - l <= k) {
if (r >= n || l >= 0 && x - arr[l] <= arr[r] - x) l--;
else r++;
}
return arr.ToList().GetRange(l + 1, k);
}
private int lower_bound(int[] nums, int num) {
int l = 0, r = nums.Length - 1;
while (l <= r) {
int m = l + r >> 1;
if (nums[m] >= num) r = m - 1;
else l = m + 1;
}
return l;
}
}int lower_bound(int* nums, int numsSize, int num) {
int l = 0, r = numsSize - 1;
while (l <= r) {
int m = l + r >> 1;
if (nums[m] >= num) r = m - 1;
else l = m + 1;
}
return l;
}
int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize){
int r = lower_bound(arr, arrSize, x), l = r - 1;
while (r - l <= k) {
r >= arrSize || l >= 0 && x - arr[l] <= arr[r] - x ? l-- : r++;
}
int* ans = malloc(sizeof(int) * k);
memcpy(ans, arr + l + 1, sizeof(int) *k);
*returnSize = k;
return ans;
}class Solution { // 自行实现 lower_bound
private:
int lower_bound(vector<int>& nums, int num) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int m = (l + r) >> 1;
if (nums[m] >= num) r = m - 1;
else l = m + 1;
}
return l;
}
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int r = lower_bound(arr, x), l = r - 1, n = arr.size();
while (r - l <= k) {
r >= n || l >= 0 && x - arr[l] <= arr[r] - x ? l-- : r++;
}
return vector<int>(arr.begin() + l + 1, arr.begin() + r);
}
};class Solution { // 使用 #include <algorithm>
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int r = lower_bound(arr.begin(), arr.end(), x) - arr.begin(), l = r - 1, n = arr.size();
while (r - l <= k) {
r >= n || l >= 0 && x - arr[l] <= arr[r] - x ? l-- : r++;
}
return vector<int>(arr.begin() + l + 1, arr.begin() + r);
}
};二分查找 · 传函数 · 直接找左边界
var findClosestElements = function(arr, k, x) {
const l = binarySearch(arr.length - k, m => x - arr[m] <= arr[m + k] - x)
return arr.slice(l, l + k)
};
const binarySearch = (r, cb) => {
let l = 0
while (l < r) {
const m = l + r >>> 1
if (cb(m)) r = m
else l = m + 1
}
return l
}func findClosestElements(arr []int, k int, x int) []int {
l := sort.Search(len(arr) - k, func(i int) bool {
return x - arr[i] <= arr[i + k] - x
})
return arr[l: l + k]
}class Solution {
function findClosestElements($arr, $k, $x) {
return array_slice($arr, $this->binarySearch(count($arr) - $k, function($m) use(&$arr, $k, $x) {
return $x - $arr[$m] <= $arr[$m + $k] - $x;
}), $k);
}
function binarySearch($r, $func) {
$l = 0;
while ($l < $r) {
$m = $l + $r >> 1;
if ($func($m)) $r = $m;
else $l = $m + 1;
}
return $l;
}
}class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
l = self.binarySearch(len(arr) - k, lambda i: x - arr[i] <= arr[i + k] - x)
return arr[l:l + k]
def binarySearch(self, r: int, func: Callable[[int], bool]) -> int:
l = 0
while l < r:
m = l + r >> 1
if func(m): r = m
else: l = m + 1
return lclass Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int l = binarySearch(arr.length - k, (i) -> x - arr[i] <= arr[i + k] - x);
return Arrays.stream(Arrays.copyOfRange(arr, l, l + k)).boxed().collect(Collectors.toList());
}
private int binarySearch(int r, Function<Integer, Boolean> func) {
int l = 0;
while (l < r) {
int m = l + r >> 1;
if (func.apply(m)) r = m;
else l = m + 1;
}
return l;
}
}public class Solution {
public IList<int> FindClosestElements(int[] arr, int k, int x) {
return arr.ToList().GetRange(BinarySearh(arr.Length - k, (i) => x - arr[i] <= arr[i + k] - x), k);
}
private int BinarySearh(int r, Func<int, bool> func) {
int l = 0;
while (l < r) {
int m = l + r >> 1;
if (func(m)) r = m;
else l = m + 1;
}
return l;
}
}bool func(int m, int** arr, int k, int x) {
return x - (*arr)[m] <= (*arr)[m + k] - x;
}
int binarySearch(int r, bool (*func)(int, int**, int, int), int** arr, int k, int x) {
int l = 0;
while(l < r) {
int m = l + r >> 1;
if (func(m, arr, k, x)) r = m;
else l = m + 1;
}
return l;
}
int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize){
int* ans = malloc(sizeof(int) * k);
int l = binarySearch(arrSize - k, func, &arr, k, x);
memcpy(ans, arr + binarySearch(arrSize - k, func, &arr, k, x), sizeof(int) * k);
*returnSize = k;
return ans;
}class Solution {
private:
int binarySearch(int r, function<bool(int)> func) {
int l = 0;
while (l < r) {
int m = (l + r) >> 1;
if (func(m)) r = m;
else l = m + 1;
}
return l;
}
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int l = binarySearch(arr.size() - k, [&arr, k, x](int m) -> bool {
return x - arr[m] <= arr[m + k] - x;
});
return vector<int>(arr.begin() + l, arr.begin() + l + k);
}
};