[LeetCode] 658. Find K Closest Elements

轉自LeetCode

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 = 3
Output: [1,2,3,4]

Example 2:

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

 

Constraints:

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

Solution

首先用 two pointers 來解

就按照題意來解，每次去計算 arr 的第一個數字，和最後一個數字，各自和 x 的差值

把離的比較遠的那個數字拿掉

kotlin(參考解法)

	class Solution {
	fun findClosestElements(arr: IntArray, k: Int, x: Int): List<Int> {
	val ans = arr.toMutableList()
	while(ans.size > k) {
	if(x - ans.first() <= ans.last() - x) {
	ans.removeAt(ans.lastIndex)
	} else {
	ans.removeAt(0)
	}
	}
	return ans
	}
	}

view raw find_k_closest_elements.kt hosted with ❤ by GitHub

另一個解法是二分法

找到值後，往左右再找到範圍

這邊可以做一個變化，讓二分法的左邊界結果，會是要找的起點

首先，right 的初始值是 arr.size() - k

想像每次檢查的範圍是 (arr[mid], arr[mid+k])，那可能有下列四種情況

x     arr[mid]        arr[mid+k]   ->  得往左移動

arr[mid]  x           arr[mid+k]   ->  得往左移動

arr[mid]         x    arr[mid+k]   ->  得往右移動

arr[mid]              arr[mid+k]   x   ->  得往右移動

也就是說，當 x - arr[mid] > arr[mid+k] - x 的時候，必須向右移動

kotlin

	class Solution {
	fun findClosestElements(arr: IntArray, k: Int, x: Int): List<Int> {
	var left = 0
	var right = arr.size - k
	while(left < right) {
	var mid = left + (right - left) / 2
	if(x - arr[mid] > arr[mid+k] - x) {
	left = mid + 1
	} else {
	right = mid
	}
	}
	return arr.copyOfRange(left, left+k).toList()
	}
	}

view raw find_k_closest_elements.kt hosted with ❤ by GitHub