Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

1. Title Description

You are given an array of integers with indices starting at 0 nums and two integers key and k. K neighbor is one of the nums subscript subscript I, and there are at least a subscript j make | I – j | < = K and nums = = [j] key.

Returns all K nearest neighbor subscripts in ascending order as a list.

Example 1:

Input: nums = [3,4,9,1,3,9,5], key = 9, k = 1 output: [1,2,3,4,5,6] description: therefore, nums[2] == key and nums[5] == key. - the subscript 0. 2 | | 0 - > k and | | 0 to 5 > k, so there is no make | 0 - j j | < = k and nums = = [j] key. So 0 is not a K nearest neighbor index. 1-2 - the subscript 1. | | < = k and nums [2] = = key, so 1 is a k neighbor subscript. 2-2 - the subscript 2. | | < = k and nums [2] = = key, so 2 is a k neighbor subscript. - to subscript 3, 2 | | 3 - < = k and nums [2] = = key, so 3 is a k neighbor subscript. 4-5 - the subscript 4. | | < = k and nums [5] = = key, so is a 4 k neighbor subscript. - to subscript 5, 5-5 | | < = k and nums [5] = = key, so 5 is a k neighbor subscript. - to subscript 6, 6-5 | | < = k and nums [5] = = key, so 6 is a k neighbor subscript. Therefore, return [1,2,3,4,5,6] in ascending order.Copy the code

Example 2:

Input: nums = [2,2,2,2], key = 2, k = 2 All the subscript nums I, there is always a subscript j make | I - j | < = k and nums = = [j] key, so each subscript is a k neighbor subscript. Therefore, return [0,1,2,3,4].Copy the code

Tip:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • keyIs an arraynumsAn integer in
  • 1 <= k <= nums.length

Second, train of thought analysis

After reading the description, my first feeling was to look for rules. K neighbor subscript refers to a subscript I, in the nums and meet there are at least a subscript j make | | I – j < = K and nums = = [j] key, that is to say, I need to find the value is the key element in the array, the element subscript, Taking this index as the midpoint and extending left and right with k as the step size, all the indices within the extended interval are the k nearest neighbor indices we are looking for.

Note that:

  • At most, the extended range extends to the array boundary, i.e[0, nums.length]Therefore, ifnumsThe first element of the array is zerokey 且 k >= 1, we need to deal with the left boundary of the extended interval, and the right boundary as well.
  • Subject to thenumsMultiple values may appear in the arraykey, so create onearrArray, set the value tokeyThe index of the element is stored in.
  • It is required that all k-nearest subscripts in ascending order be returned as a list. The ascending order is preserved by traversing the array from left to right, so this condition is ignored.
  • Since there may be multiple values ofkeyIn order not to have duplicate elements in the result array, you can useSetduplicate removal

The problem solving process is as follows:

  1. createarrArray andresArray,arrUsed to store the valuekeyThe elements,resUsed to store all K neighbor subscripts.
  2. traversenumsArray, where the value iskeyElement, subscript the elementpush 进 arrThe array.
  3. traversearrArray that determines to have the current element as the midpoint, andkIs the extended interval of step size, and attention should be paid to the range of processing interval.
  4. Values within the range of the interval (equivalent tonumsElement subscript of array)push 进 resThe array.
  5. rightresArray to complete the problem.

AC code

/ * * *@param {number[]} nums
 * @param {number} key
 * @param {number} k
 * @return {number[]}* /
var findKDistantIndices = function(nums, key, k) {
    let arr = [], res = [];
    for (let i = 0; i < nums.length; i++) {
        if(nums[i] === key) { arr.push(i); }}for (let i = 0; i < arr.length; i++) {
        let num = arr[i] - k >= 0 ? arr[i] - k : 0;
        while(num <= arr[i] + k && num < nums.length) { res.push(num++); }}return Array.from(new Set(res));
};
Copy the code

Four,

Do the problem at present according to the requirements and information to find rules, have ideas and then start to knock code will be a lot better.

I wish you all problem AC, bug all disappear!!