https://leetcode.com/problems/find-k-closest-elements/description/
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. x比arr中最小的元素还小，那么显然取arr中前K个。
2. x比arr中最大的元素还大，那么显然去arr中后k个。
3. x在arr的范围中，那么就需要找到最靠近arr的那个点。
如何找最靠近的点，不就是二分查找吗？能找到相等的就是它了，或者就是比他小一点的那个。这里和Search Insert Position类似，却又不同。
然后想到，1和2其实也可以包含在3中了。
这样，找到了这个最靠近的点，如何找其他k-1个？
开始简单的认为贪心往前找，随后剩下的再往后。这样是不对的，什么叫closest？这样假设arr中的数字都是连续的了（相邻的相差1）。
class Solution { public List<Integer> findClosestElements(int[] arr, int k, int x) { List<Integer> res = new ArrayList<Integer>(); // 找到x所在的index，或者比他小的那个index int neareastIndex = findNearestIndex(arr, x); // 两种情况需要往前移一个 if (neareastIndex >= arr.length || arr[neareastIndex] > x) { if (neareastIndex > 0) { neareastIndex--; } } int count = 1; int index = neareastIndex, left = neareastIndex - 1, right = neareastIndex + 1; //res.add(arr[index]); while (count < k) { if (left >= 0 && right < arr.length) { if (x - arr[left] <= arr[right] - x) { //res.add(0, arr[left]); left--; } else { //res.add(arr[right]); right++; } } else if (left >= 0) { //res.add(0, arr[left]); left--; } else { //res.add(arr[right]); right++; } count++; } for (int i = left + 1; i < right; i++) { res.add(arr[i]); } return res; } public int findNearestIndex(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] > target) { right = mid - 1; } else if (arr[mid] < target) { left = mid + 1; } } return left; } }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。