A few days ago, Ruan Yifeng and Winter organized a face-to-face group in the front nine, the purpose is to share and answer the interview questions encountered in the interview, you can know about it.

I’m going to share with you one of the questions I answered.

Problem description

The title is: Algorithms, the first K largest elements.

The topic is so short that at first glance you may not know what it means. Translation:

Given an array of numeric type and a positive integer K, find the first K largest elements in the array.

This topic network speed also has a lot of explanation, I am also based on the Internet to provide some ideas to achieve, the following is my implementation according to the three methods:

answer

Solution a:

Train of thought

The easiest way to do this is to sort the array and take the first K bits.

implementation

/** @param {number[]} arr - Array to query * @param {number} K - Maximum number ** @return {number[]} */
const findKMax = (arr, k) = > {
  return arr.sort((a, b) = > b - a).slice(0, k);
}
Copy the code

Method 2

Train of thought

Solution one uses JS sort to achieve sorting, but the complexity is relatively high, the data will be slow. I’m going to go through the problem and find the first K largest elements, but I’m not asking you to sort them, so I don’t have to sort all of them. Divide-and-conquer is much faster:

Suppose there are n numbers in the array S, select a random element X from the array S, and iterate over the number set. Those larger than X are placed in S1, and those smaller than X are placed in S2, then the following three situations will occur:

The number of S1 numbers is equal to K, the search ends, return S1; If the number of S1 numbers is greater than K, continue to find the largest K number in S1. If the number of S1 is less than K, continue to find the largest k-s1. length number in S2 and splice it after S1. So if we keep recursing, we can figure out the answer. Let’s look at the implementation:

implementation

/** @typedef {Object} Partition * @property {number[]} Partition. Maxarr * @property {number[]} Partition. Minarr * * @param {number[]} arr - Array to be split * * @returns {Partition} res - Returns result */
const partition = (arr) = > {
  const length = arr.length; // Array length

  const mid = ~~(length / 2); // Take the middle position of the array, optionally
  const middle = arr[mid]; // The middle value of the array
  const maxarr = []; // Greater than the median value
  const minarr = []; // Less than the median value

  // Arrays of length 2 are treated specially
  if (length === 2) {
    maxarr.push(Math.max(arr[0], arr[1]));
    minarr.push(Math.min(arr[0], arr[1]));
  } else {
    arr.forEach((v, i) = > {
      if(i ! == mid) {if (v >= middle) {
          maxarr.push(v);
        } else{ minarr.push(v); }}})// Place the median value in the last digit of maxarr
    maxarr.push(middle);
  }

  return { maxarr, minarr }
}

/** @param {number[]} arr - Array to query * @param {number} K - Maximum number ** @return {number[]} */
const findKMax = (arr, k) = > {

  if (arr.length < k) {
    return arr;
  }

  // Split the array
  const { maxarr, minarr } = partition(arr);

  if (maxarr.length === k) {
    return maxarr;
  }

  if (maxarr.length > k) {
    return findKMax(maxarr, k);
  }

  if (maxarr.length < k) {
    returnmaxarr.concat(findKMax(minarr, k - maxarr.length)); }}Copy the code

Method three

Train of thought

Can take an array of K bit before building a small pile of (also called the minimum heap), so before the pile top is K a minimum value, then from K + 1 times the array, if less than the pile top, the exchange, and rebuild the heap, minimize the pile top, after the traversal, so is the greatest pile K bit, pile top is the minimum value of K bit before.

implementation

@param {number[]} arr - heap * @param {number} I = parent node * @param {length} I - heap size */
const heapify = (arr, i, length) = > {
  const left = 2 * i + 1; // Left child node
  const right = 2 * i + 2; // Right child node
  let minimum = i; // Assume that the smallest node is the parent

  // Determine the minimum of the three nodes
  if (left < length && arr[left] < arr[minimum]) {
    minimum = left;
  }

  if (right < length && arr[right] < arr[minimum]) {
    minimum = right;
  }

  // If the parent node is not the smallest node
  if(minimum ! == i) {// The smallest node swaps with the parent node
    const tmp = arr[minimum];
    arr[minimum] = arr[i];
    arr[i] = tmp;

    // Do the same swap for the adjusted nodeheapify(arr, minimum, length); }}/** * Build the small top heap * build the heap from n/2 nodes until the first node ** @param {number[]} arr */
const buildMinHeap = (arr) = > {
  for (let i = Math.floor(arr.length / 2); i >= 0; i--) {
    heapify(arr, i, arr.length)
  }
  return arr;
}

/** @param {number[]} arr - Array to be queried * @param {number} K - Maximum number ** @return {number[]} */
const findKMax = (arr, k) = > {
  // Take the first K bits of the array and build the small top heap
  const newArr = [...arr];
  const kMax = arr.slice(0, k)
  buildMinHeap(kMax);

  If it is larger than the top of the heap, the heap is swapped and rebuilt
  for (let i = k; i < newArr.length; i++) {
    if (newArr[i] > kMax[0]) {
      const tmp = kMax[0];
      kMax[0] = newArr[i]; newArr[i] = tmp; buildMinHeap(kMax); }}return kMax;
}
Copy the code

conclusion

Above is my three kinds of solutions to this topic, in fact, there are several solutions, because energy reasons did not explore, we can go to the Internet to understand.

Please correct the above solution if there is any problem.