This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

2. How to solve the problem

1. Sorting algorithm

Speaking of sorting, it must be using a sorting algorithm!

Time complexity analysis

Suppose you use quicksort

  • O(nlogn)

Spatial complexity analysis

Suppose you use quicksort

  • O(1)

2. Single pointer

Can you think of any other optimization direction? Available information:

  • There are only three colors, so there are only 0,1,2 numbers
  • Sorted by red, white and blue, so 0,1,2

If we only have three numbers, then we scan the array with Pointers and put zeros to the left and twos to the right. So we can scan twice, the first time we move the 0 to the left, and the second time we move the 2 to the right.

Time complexity analysis

  • O(2n)

Spatial complexity analysis

  • O(1)

3. Double pointer

We find that the single pointer does nothing when the first scan reaches 2, so two scans are required. So can we sort it in one scan? The answer is yes. We can add a pointer to the position of 1 (or 2).

Time complexity analysis

  • O(n)

Spatial complexity analysis

  • O(1)

Three, code implementation

class Solution { public void sortColors(int[] nums) { int n = nums.length; int p0 = 0, p1 = 0; for (int i = 0; i < n; ++i) { if (nums[i] == 1) { int temp = nums[i]; nums[i] = nums[p1]; nums[p1] = temp; ++p1; } else if (nums[i] == 0) { int temp = nums[i]; nums[i] = nums[p0]; nums[p0] = temp; if (p0 < p1) { temp = nums[i]; nums[i] = nums[p1]; nums[p1] = temp; } ++p0; ++p1; }}}}Copy the code

I don’t know if I have made myself clear, please give me more advice. Punch out for the day!