Title link: leetcode-cn.com/problems/re…

Their thinking

This is a sorting problem, so the first thing we should think about is some common sorting algorithms. It is mainly divided into two categories. One is the sorting algorithm based on comparison, such as quicksort and heap sort. The other kind of sorting algorithm is not based on comparison, including counting sort and bucket sort. The optimization time complexity of sorting algorithm based on comparison can not be less than. However, non-comparison-based sorting algorithms can achieve lower time complexity.

Comparison – based sorting algorithm is more widely used in a wide range of scenarios, but non-comparison – based sorting algorithm has its own limitations, only applicable to conditional scenarios, such as limiting the size of elements. Array size and element size are limited.

I’m not going to go into the details of counting sorting, so if you don’t understand it, you can look it up, but I’ll try to make it as simple as possible.

The solution is as follows:

  1. First of all, we need to fully understand the requirements and intentions of the questionThe elements inAnd exists only inThe elements in the, need to be placed in order from smallest to largestAt the end.
  2. becauseThe number of occurrences of each element in, counted the occurrence times of each element and recorded in,The subscript of the element inIs the value of the element being counted,It’s one of our intermediate arrays. For example,The value ofThe element appearsSo let’s do the statistics and get.
  3. So let’s go through, it is assumed thatThe element in is, then ifarr[num] ! = = 0On the other hand, indicateAnd the value isIs not sorted, so we canans.push(num)And at the same timearr[num]--. This completes the followingPairs the order of elements inTo sort the elements in.
  4. The traverseAnd will beIn, but not inElements are appended to, in descending orderAnd finally returnsYou get the sorted array.
  5. The range of array lengths is fixed, so we can declare an intermediate array of fixed lengthsnew Int8Array(1001)The statementType. I’m going to set its length to be zeroBecause arrayThe subscript and, and its element maximum value is.

code

/** * @param {number[]} arr1 * @param {number[]} arr2 * @return {number[]} */
var relativeSortArray = function(arr1, arr2) {
    let arr = new Int8Array(1001);
    let ans = [];

    for (let i = 0; i < arr1.length; i++) {
        arr[arr1[i]]++;
    }

    for (let num of arr2) {
        while(arr[num] ! = =0) { ans.push(num); arr[num]--; }}for (let i = 0; i < arr.length; i++) {
        while(arr[i] ! = =0) { ans.push(i); arr[i]--; }}return ans;
};
Copy the code

Complexity analysis:

  • Time complexity:
  • Space complexity:

Among themAs an arrayThe length of theAs an arrayThe length of the.

More questions please pay attention to: github.com/leviding/le…

Pay attention to the public number “technology chatter” plus algorithm group, every day an algorithm, fun algorithm is very easy! :

  • LeetCode algorithm problem solving
  • JavaScript getting started to advanced
  • Front-end projects go from zero to one
  • Front end learning method route sharing
  • …