658. Find K Closest Elements

• 658. Find K Closest Elements
  • Description
  • Intuition
  • Pitfall
  • Solution

Description

Here

Intuition

先上结论, the subarray starts the first occurrence of t, where x - nums[t] <= nums[t + k] - x

如果左侧有更optimal的，比如左侧1，那么要移进去nums[t - 1], 移出 nums[t + k - 1]，那么意味着x - nums[t - 1] <= nums[t - k - 1] - x，与第一个满足此条件矛盾

如果右侧有更好的，比如右侧1，那么要移进去nums[t + k], 移出 nums[t]，那么意味着x - nums[t] > nums[t + k] - x，与条件本身相矛盾

Pitfall

这里有个坑，被避免了。中途有个检查条件（即 //first astisfy那一行）照道理应该检查nums[mid + k]是否在range里，但是凑巧的是，这个mid的计算方法，始终保持指向preMid，那么在计算中不可能指向最后一个元素，使得out of boundary发生

Solution

Solution

  public List<Integer> findClosestElements(int[] nums, int k, int x) {
    // The value k is positive and will always be smaller than the length of the sorted array.
    if (k == 0 || nums == null || nums.length == 0) {
      return new ArrayList<>();
    }
    int left = 0, right = nums.length - k;
    while (left < right) {
      final int mid = (right - left) / 2 + left;
      if (x - nums[mid] <= nums[mid + k] - x) { // first satisfy
        right = mid;
      } else {
        left = mid + 1;
      }
    }
//    assert (x - nums[left] <= nums[left + k] - x);
    final List<Integer> result = new ArrayList<>();
    for (int i = 0; i < k; i++) {
      result.add(nums[left + i]);
    }
    return result;
  }