This is the 8th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Color classification (Question Number 75)

The title

Given an array of n red, white, and blue elements, sort them in place so that elements of the same color are next to each other in red, white, and blue order.

In this case, we use the integers 0, 1 and 2 to represent red, white and blue, respectively.

Example 1:

Input: nums = [2.0.2.1.1.0] Output: [0.0.1.1.2.2]
Copy the code

Example 2:

Input: nums = [2.0.1] Output: [0.1.2]
Copy the code

Example 3:

Input: nums = [0] Output: [0]
Copy the code

Example 4:

Input: nums = [1] Output: [1]
Copy the code

Tip:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] δΈΊ 0,1 ζˆ– 2

Advanced:

  • Can you solve this problem without using the sorting functions in the code base?
  • Can you think of an algorithm that uses only constant space for one scan?

link

Leetcode-cn.com/problems/so…

explain

This one, this is a classic sort.

The problem is to translate a random number group composed of 0, 1, 2, put it in the same place in ascending order, the whole red, white and blue.

Sorting is easy, there are many ways to sort, the classic one is sort, but notice the advanced hints here, it requires not the default sort, and it requires space complexity O(1) and time complexity O(n).

Because of the solution of this problem by many kinds, here will not expand the analysis, detailed analysis in the following specific answers.

Your own answers (sort)

That’s easy πŸ‘‡ :

function sortColors(nums) {
  return nums.sort((a, b) = > a - b)
}
Copy the code

In order to print out the result, return the result, which is not a big problem.

Your own answers (Map)

You can create a new Map to store the number of occurrences of each type in the array, and then modify the array according to the Map.

This scheme is obviously feasible, because the author immediately thought of πŸ‘‡ :

function sortColors(nums) {
  const map = new Map(a)for (const v of nums) {
    if(! map.has(v)) map.set(v,0)
    map.set(v, map.get(v) + 1)}const valArr = [...map].sort((a, b) = > a[0] - b[0])
  let i = 0
  for (const item of valArr) {
    let count = item[1]
    const color = item[0]
    while (count > 0) {
      nums[i] = color
      i++
      count--
    }
  }
  return nums
}
Copy the code

In the code for πŸ‘†, we first scan through the source array to get the frequency of each number and store it in the Map.

Then we sort the values of the Map, because it’s possible to store them out of order, and here we need to sort them in ascending order, so we sort the results.

For chestnut, if the array is sauce aunts:,0,2,1,1,0 [2], then valArr’s: [[0, 2], [1, 2], [2, 2]].

This is what the final array should look like.

Next, use I as the replacement position, keep updating the current position, inside the second for loop, do a while loop for each number, and then you’re done.

After that, numS is the sorted result.

Better method (single pointer)

So that’s the official answer, using a pointer, loop twice.

The pointer starts at the first digit of the array and loops through it. When a zero is encountered, the current digit is swapped with the position of the pointer. After the loop, all the zeros in the array are moved to the left.

Then we start a second loop, starting at the pointer’s position, and when we encounter a 1, we swap the number at the current position with the pointer’s position, and if we’re done, the 1 will appear after the 0 in the array.

The array is sorted by scanning it twice. The code is πŸ‘‡ :

function sortColors(nums) {
  const len = nums.length
  let ptr = 0
  for (let i = 0; i < len; i++) {
    if (nums[i] === 0) {
      [nums[i], nums[ptr]] = [nums[ptr], nums[i]]
      ptr++
    }    
  }
  for (let i = ptr; i < len; i++) {
    if (nums[i] === 1) {
      [nums[i], nums[ptr]] = [nums[ptr], nums[i]]
      ptr++
    }    
  }
  return nums
}
Copy the code

Better method (double pointer (0, 1))

In a single-pointer method, the array is actually swept twice, which does not meet the advanced requirements, so there is no way to scan once to solve the battle? Obviously there is. It’s a double pointer.

We have two Pointers, p0 and P1, where p0 is where 0 is, and P1 is where 1 is.

Now, starting from scratch, the numbers will appear in three ways:

  • 2

    Ignore it, skip it

  • 1

    If it’s 1, swap the current number with the number at the p1 pointer, because it starts at the first digit of the array, so if it comes first, it’s now concentrated on the leftmost part of the array, and notice that this is related to the 0 rule below

  • 0

    If it’s zero, the default is to replace the number at p0 with the current number, but there’s a problem here, is there a problem if P0 is in front of p1?

    The 0 is actually where it’s supposed to be, but the 1 is where the loop is now, and if we continue, we’re going to skip the 1, and we’re going to have a problem with the order of the array

    In order to solve this situation, you need to make a judgment. If P0 <= p1, you need to replace the number in the position of the p1 pointer with the 1 that you just replaced with 0, and add 1, so that the order of 0 and 1 is correct.

Although a lot of text, in fact, very little code πŸ‘‡ :

function sortColors(nums) {
  const len = nums.length
  let p0 = 0, p1 = 0
  for (let i = 0; i < len; i++) {
    if (nums[i] === 1) {
      [nums[i], nums[p1]] = [nums[p1], nums[i]]
      p1++
    } else if (nums[i] === 0) {
      [nums[i], nums[p0]] = [nums[p0], nums[i]]
      if (p0 < p1) {
        [nums[i], nums[p1]] = [nums[p1], nums[i]]
      }
      p0++
      p1++
    }
  }
  return nums
}
Copy the code

The 0 and 1 cases mentioned above can be treated separately.

Better method (double pointer (0, 2))

With a pointer to 0 and a pointer to 1, we can naturally have a pointer to 0 and a pointer to 2, but since 1 and 2 are in different positions, the pointer to 2 needs to start at the end of the array, so we can declare two Pointers like this:

const len = nums.length
let p0 = 0, p1 = len -1
Copy the code

Next, start the loop. The overall logic looks like this:

  • 0

    As with the πŸ‘† method, the number of the p0 pointer is interchanged.

  • 1

    Since there is no p1 pointer, regardless, skip

  • 2

    2 is supposed to be a simple substitution for the number where P2 is located, but there might be a problem. What if P2 starts at 2? Or is the number where the p2 pointer is currently located 2? In this case, it doesn’t really make any difference, and that’s where the problem arises.

    In order to guarantee the p2 pointer to the right of the number is 2, and the current position of the Numbers is not 2, each cycle when the need for a polling operation, update the position of the pointer to p2, the condition is that the current position number is 2, and I should be less than or equal to p2, because according to the overall logic, two Pointers are also began to move, if I run behind the p2, So we’re done, and that’s because we made sure that all the numbers to the right of P2 are 2

This is the logical part of the explanation, πŸ‘‡ look at the code:

function sortColors(nums) {
  const len = nums.length
  let p0 = 0, p2 = len - 1
  for (let i = 0; i <= p2; i++) {
    while (i <= p2 && nums[i] === 2) {
      [nums[i], nums[p2]] = [nums[p2], nums[i]]
      p2--
    }
    if (nums[i] === 0) {
      [nums[i], nums[p0]] = [nums[p0], nums[i]]
      p0++
    }
  }
  return nums
}
Copy the code

In general, the logic of the three pointer methods is similar, except that the logic of p1 and P2 is different, and the logic of P0 is always the same.

The Map method provided by the author, although it scans the array twice to some extent, can be used in the case of more types of numbers, and the pointer type method is limited to use under the problem.




PS: To view past articles and titles, click on the link below:

Here’s πŸ‘‡ by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of πŸ‘‡

Front brush problem path – Catalogue (Question type classification)