This article originated from personal public account: TechFlow, original is not easy, for attention


LeetCode: Sort Colors

The official difficulty of this question is Medium, with a pass rate of 45%, 2,955 thumbs up and 209 thumbs down (international version data). From this data, we can probably see that this question is not difficult, and the number of thumbs up is far higher than the number of thumbs down, indicating that the quality of the question is very good. And indeed, it’s simple enough and interesting enough to be worth doing.

The question

Given an array of n elements, each element in the array represents a color. There are three colors, red, white and blue, represented by 0,1 and 2. Ask to sort the colors by size and return the sorted result.

The sort library sort cannot be called to resolve the problem.

Bucket sort

If there were no restrictions on using sort, this would be easy. If we can’t call sort, we can’t write sort ourselves. Python can write a quicktypeset in just a few lines.

It is possible to write sort yourself, which is obviously the next best thing. Since elements have only three values and only a few size relationships between them, sorting is unnecessary. It’s easy to think, we can count the number of occurrences of these three numbers, how many zeros, how many ones, how many twos, and then we can put them together and restore the previous data, right?

This works, but it’s actually a sort scheme called radix sort, also known as bucket sort, and in some places it’s called pupil sort. The idea of radix sort is very simple: we create an array and use each of its bits to indicate whether an element has been present in the array before. If it happens, it’s +1, if it doesn’t, it’s always 0. After we mark the original array, we iterate over the marked array, because the indices are naturally ordered, so we can get the sorted result.

It doesn’t matter if you’re a little confused, we’ll write the code to see that since this problem requires us to provide an inplace method, we’ll need to reassign the elements in nums at the end.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        "" "        Do not return anything, modify nums in-place instead.
"" "
 bucket = [0 for _ in range(3)]  for i in nums:  bucket[i] += 1   ret = []  for i in range(3) : ret += [i] * bucket[i]   nums[:] = ret[:] Copy the code

Instead of sorting, we just iterate through the data twice, first iterating through the array to get the numbers 0,1, and 2, and then repopulating the data back into the array. Compared to quicksort or some other sort algorithmTime spent sorting bucketsThe array is only iterated twiceObviously much faster. But unfortunately, that’s not the best way to do it, because they explicitly say, well, there’s also a way to only iterate through the array once.

two pointers

Before we go into the actual algorithm, let’s analyze the problem. Since there are only three colors, when we’re done sorting, the array will be divided into three parts, with a head of 0, a middle of 1, and a tail of 2.

We can shrink the range of 1 with an interval, assuming that our current interval starts with l and ends with R. When we get to zero, we swap it with l, and then we move l back one bit. When we get to 2, we swap it with r, we move r one bit to the left. In other words, we guarantee that the element between L and r is only 1.

We have introduced this method of maintaining an interval before, although they are maintaining an interval, but there are some differences in operation. The aforementioned Two Pointers algorithm, also known as the ruler method, essentially moves the right boundary of the interval to accommodate new elements and maintains the legitimacy of all elements within the interval by moving the left boundary to pop up data. In the current case, we start with an illegal interval, and we make it legal by traversing the element and moving the interval. The idea is slightly different, but the form is the same, which is to maintain or achieve legitimacy by moving the left and right sides of the boundary.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        "" "        Do not return anything, modify nums in-place instead.
"" "
 l, r = 0, len(nums)- 1  i = 0  while i < len(nums):  if i > r:  break  If you encounter a 0, swap with the left  if nums[i] == 0:  nums[l], nums[i] = nums[i], nums[l]  l += 1  # If you encounter a 2, switch to the right  I need minus 1, because I might get a 0  elif nums[i] == 2:  nums[r], nums[i] = nums[i], nums[r]  r -= 1  continue  i += 1 Copy the code

This way we only iterate through the array once, but because ofToo many swaps, the overall running speed is even slower than the above method. So traversing an array twice isn’t necessarily worse than traversing it once, because it’s bothThe difference is just a constant. The number of iterations is just one part of the constant.

In addition to this method, there are other ways to maintain intervals.

Maintenance interval

The following method is very clever, and I personally think even more clever than the above method.

Let’s imagine a scenario where, instead of manipulating data on an array, we read data from it and put it into a new array. Instead of thinking about how to place the data, let’s assume that we already have a number of data in the original array. What would the new array look like? Obviously, it should be sorted, with a bunch of zeros in the front, a bunch of ones in the middle, and a bunch of twos at the end.

So the question is, suppose we read a zero at this point, where should we put it? To simplify the statement let’s draw it as a graph:


Let’s say the blue part is 0, the green part is 1, and the pink part is 2. A is the right-most subscript of 0, b is the right-most subscript of part 1, and C is the right-most subscript of part 2. So at this point, when we need to put in a 0, what do we do?

So it’s easy to figure out from the diagram, we need to put the 0’s in a plus 1’s position, so we need to move the 1’s and the 2’s one space to the right, to make room for the 0’s. Moving the array would obviously be too expensive, so we don’t really need to move the whole thing, just the top and bottom elements. For example, if the left side of a 1 is occupied by a 0, then in order to keep the length the same, the right side needs to be extended by one. In the same way, 2 has to be extended one space to the right. Nums [a+1] = 0, nums[b+1] = 1, nums[c+1] = 2.

Let’s say we read 1, and we need to extend b by 1, but the consequence of that is that the 2 is encroached, so we need to extend 2 as well, to make up for the encroached 1. If you read a 2, you can just extend it by 2 because there are no other colors after 2.

Let’s say we have a blank array, we can do this, but we don’t have to create an array, we can just fill ourselves in with the original array. Since the number we read from the original array is the same as the number we put in it, we simply place the number at the head of the original array, occupying the number we read previously.

It may be a little confusing, but a look at the code will make it clear:

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        "" "        Do not return anything, modify nums in-place instead.
"" "
 Record the end positions of 0,1, and 2  zero, one, two = - 1.- 1.- 1  n = len(nums)  for i in range(n):  # if 0 is placed  So move the 1 and 2 back one bit, leaving a space for the 0  if nums[i] == 0:  nums[two+1] = 2  nums[one+1] = 1  nums[zero+1] = 0  zero += 1  one += 1  two += 1  elif nums[i] == 1:  nums[two+1] = 2  nums[one+1] = 1  one += 1  two += 1  else:  nums[two+1] = 2  two += 1 Copy the code

conclusion

So now we’re basically done with this problem.

I believe you can see, from the difficulty of this problem is really not difficult, I believe you can come up with a solution, but to think of the optimal solution is still a little difficult. On the one hand, we need to have a very deep understanding of the topic, on the other hand, we also need a lot of thinking. This kind of problem has no fixed solution, we need to design solutions according to the requirements of the problem and the actual situation, which is the most test of thinking ability and algorithm design ability of the problem, than to investigate whether an algorithm will be much more interesting.

Hope everyone can enjoy this problem, if you like this article, if you can, please click on the following, give me a little encouragement, but also convenient to get more articles.

This article is formatted using MDNICE