Make writing a habit together! This is the second day of my participation in the “Gold Digging Day New Plan · April More text challenge”. Click here for more details.

Daily brush 2021.04.02

  • Leetcode: leetcode-cn.com/problems/so…
  • Difficulty: Medium
  • Method: double pointer

The title

  • Given an array of n elements, numS, in red, white, and blue, sort them in place so that elements of the same color are adjacent and sorted in red, white, and blue order.
  • We use integers 0, 1, and 2 to represent red, white, and blue, respectively.
  • You must solve this problem without using the library’s sort function.

The sample

  • 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

prompt

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0,1 或 2

Their thinking

  • Thinking analysis: Need to be able to quickly sort ideas.
  • In the loop variableiIn traversal, the invariant properties of defined loops are considered to determine the initialization, traversal, and loop termination conditions

Subject train of thought

  • Initialization: three intervals
    • [0,l)=> l all elements before l are 0
    • [l,r]=> All intermediate values are 1
    • (r,len - 1]All values after r are 2
    • Analysis: All the three intervals should be set to 0 during initialization, that is:l = 0, r = len - 1At this point, the three intervals cover the entire array
  • Traversal process: An intermediate variable is requiredi
    • whennums[i] == 0, you need to put it in the first interval
    • whennums[i] == 2, it needs to be placed in the third interval
    • In the middle of the1No need to change
    • Pay attention to: left after the exchange, need to beiLeave it at the current location
  • Loop termination: wheni > r
    • Why? Because: the third interval(r, len- 1], it has been determined that all of them are arranged2, so there is no need to continue to judge later, meaningless.

ACcode

var sortColors = function(nums) {
  // Three intervals: one on the left, one in the middle, one on the right
  let len = nums.length;
  let l = 0, r = len - 1,i = 0;
  while(i <= r) {
    if(nums[i] == 0) {let tempt = nums[l];
      nums[l] = nums[i];
      nums[i] = tempt;
      l++;
    }else if(nums[i] == 2) {// console.log(r,nums[r],i,nums[i])
      let tt = nums[r];
      nums[r] = nums[i];
      nums[i] = tt;
      // console.log('arr:', nums)r--; i--; } i++; }};Copy the code

conclusion

  • Loop invariants are the basis for writing correct code and analyzing boundary conditions