This is an algorithm encountered in the front-end interview process, although it is not difficult, but there are some details that need to be carefully considered.

For example, in the array [1, 2, 4, 4, 3, 5], the second largest number is 4, which occurs twice. Here’s an example of how to expand the algorithm.

Talk about the general idea first, and then consider some details.

  • Since the problem of number size is involved, it is necessary to sort the given array. The problem requires the “KTH largest” number, so the way of choosing descending order is more conducive to the subsequent search.

  • If the rank is greater than k, the loop ends. If the rank is greater than k, the loop ends. If the rank is equal to the k value, the array element is denoted as the KTH largest number and the degree is incremented by one;

  • So how do you determine the size ranking of the current array elements being iterated over? We first set the first item of the array as the first largest number, and then compare the first and second items to see if they are equal. If they are equal, the second item is also the first largest number. If not, the second item in the array is the second largest number. By analogy, the size ranking of array elements traversed each time can be obtained.

Now that we’re done with the general idea, let’s look at the details — boundary judgment

  • Whether the given k value is greater than or equal to 1 (no 0th digit is guaranteed) and less than or equal to the length of the array (because the smallest element cannot be larger than the length of the array if the array is sorted in descending order). This judgment implies that the array cannot be empty.

  • At the end of the loop, k cannot exceed the rank of the smallest element in the array. If it does, there is no such number in the array.

According to the above ideas and details, the algorithm is as follows:

function findKthNum (arr, k) {
  var len = arr.length;
  // Make sure len >= k >= 1
  if (k > len || k < 1) {
    console.log("There doesn't exists the number you want !");
    return;
  }
  // Get a copy of the array
  var _arr = arr.slice();
  // The size ranking of the current array elements when iterating through the array
  var rank = 1;
  // The KTH largest number
  var num = 0;
  // The number of occurrences of the KTH large number
  var count = 0;
  // Sort _arr in descending order
  _arr.sort(function (a, b) {
    return b - a;
  });
  for (var i = 0; i < len; i++) {
    var j = i + 1;
    // Compare the size rank of the current array elements with the k value, if the rank is large
    // end the loop at k; If the ranking is equal to the k value, the array is divided
    // The element is the KTH largest number and the degree is increased by one.
    if (rank > k) {
      break;
    } else if (rank == k) {
      num = _arr[i];
      count++;
    }
    // If the current item is not equal to the next item, the next item is specified
    // The ranking value of the number is exactly 1 greater than the ranking of the currently traversed number
    if ((j < len) && (_arr[i] != _arr[j])) {
      rank++;
    }
  }
  // At the end of the loop, if the size ranking of the last array element is less than the given k value, then it is said
  // There is no KTH digit in the explicit array, that is, the value of k exceeds the size ranking of all array elements.
  if (rank < k) {
    console.log("There doesn't exists the number you want !");
  } else {
    console.log('the first' + k + 'Big numbers:' + num, 'Number of occurrences:'+ count); }}Copy the code

Finally, some test cases are given:

// findKthNum(arr1, 2)
var arr1 = [1.2.4.4.3.5];

FindKthNum (arr2, 2)
var arr2 = [];

FindKthNum (arr3, 0);
var arr3 = [1.2.4.4.3.5];

FindKthNum (arr4, 7)
var arr4 = [1.2.4.4.3.5];

FindKthNum (arr5, 6) findKthNum(arr5, 6)
var arr5 = [1.2.4.4.3.5];
Copy the code