Subject to introduce

This problem is LeetCode75.

Given an array of n red, white, and blue elements, sort them in place so that the elements of the same color are adjacent and sorted in red, white, and blue order.

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

Example 1:

Input: nums = [2,0,2,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] is 0, 1, or 2

 

Advanced:

  • Can you solve this problem without using the collation function in the code base?
  • Can you come up with a one-pass scan algorithm that uses only constant space?

Their thinking

(nums = 0, 1, 2) (nums = 0, 1, 2) (numS = 0, 1, 2) (numS = 0, 1, 2) (numS = 0, 1, 2) (numS = 0, 1, 2)

That’s where we swap arrays with Pointers.

Single needle

Set a pointer to PTR = 0, then loop through the numS array, find each 0 and PTR ++ swap, the end of the loop numS array header is 0.

Then loop through the numS array again, starting with PTR, swapping each 1 with PTR, without swapping PTR ++, and the numS array is the desired result.

Time complexity: O(n)O(n), where nn is the length of array \textit{nums}nums.

Space complexity: O(1)O(1).

Double pointer

A single pointer is a pointer PTR that loops twice. Can we loop only once?

Can, of course, set two Pointers p0 = 0, p1 = 0, then loop nums array, if meet 0 we will I and p0 exchange, pay attention to here, because we are according to 0, 1, 2 order to sorting, so after 0 is 1, we may put 1 swapped out here, so here when p0 < p1, We also need to swap I with P1, and then p0++; P1 + +.

If we meet 1, then we swap p1 and I just like we did with a single pointer, and then p1++;

So finally we have the array that we want.

Left and right double pointer

Left = 0 and right = nums. length-1. Stop traversing when right is exceeded.

When you hit zero, you swap I and left, and then left++.

When you meet 2, you swap I and right, and then right–.

1 stays the same, and the array nums at the end of the loop is the result array we need.

The problem solving code

Single needle

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

Double pointer

var sortColors1 = function(nums) {
  const n = nums.length;
  let p0 = 0, p1 = 0;
  for (let i = 0; i < n; 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

Double pointer

var sortColors2 = function(nums) {
  const n = nums.length;
  let left = 0, right = n - 1;
  let i = 0;
  while(i <= right) {
    while(i <= right && nums[i] === 2) {
      [nums[i], nums[right]] = [nums[right], nums[i]];
      right--;
    }
    if (nums[i] === 0) {
      [nums[i], nums[left]] = [nums[left], nums[i]];
      left++;
    }
    i++;
  }
  return nums;
}
Copy the code

Swipe questions and punch out records

Here is the previous swipe card records, you can have a look, if you have any different views and views or feel what is wrong, welcome to leave a message in the comment area! 🙏 🙏 🙏

[LeetCode0303 topic area and retrieval – array immutable] | punch brush

[LeetCode1200. Minimum absolute difference] | punch brush

[LeetCode0304 topic 2 d area and retrieval – matrix immutable] | punch brush

[LeetCode11 topic containers of most water] | punch brush

[LeetCode0338 topic bit count] | punch brush

[LeetCode209 topic length minimum subarray] | punch brush

[LeetCode236 topic in recent common ancestor of binary tree] | punch brush

[LeetCode141 topic circular linked list] | punch brush

[LeetCode53 topic most architectural sequence and] | punch brush

[LeetCode48 topic rotating images] | punch brush

[LeetCode155 topic minimum stack] | punch brush

[LeetCode1124 problem well, the longest period of a] | punch brush

[LeetCode274 problem H index] | punch brush

[LeetCode367 problem effective completely square number] | punch brush

[LeetCode1047 problem delete all adjacent duplicates of the string] | punch brush

[LeetCode160 topic cross linked list] | punch brush

[LeetCode1438 topic absolute difference does not exceed the limit of the longest continuous subarray] | punch brush

[LeetCode434 problem the number of words in a string] | punch brush

conclusion

Come on! HXDM!!!!!! 💪 💪 💪

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign