[leetcode]75. color classification - problem solving (execution time beat 90%, memory consumption beat 78%)

01

Title Description

Give one that contains red 、 White and blue , altogether n Array of elements , Sort them in place , Make elements of the same color adjacent , And follow the red 、 white 、 In blue order . In this question , We use integers 0、 1 and 2 Red... Respectively 、 White and blue .

Be careful : You can't use the sort function in the code base to solve this problem .

Example :

Input : [2,0,2,1,1,0]

Output : [0,0,1,1,2,2]

02

analysis

obviously , The most intuitive method is to count through one-time traversal 0、1、2 The number of , Again according to 0、1、2 Rewrite the array in the order of . But this method requires two scans . Is there a way to complete the arrangement by one scan ？ The answer is ： Yes ！

problem 1： What's the idea ？

Observe the output of the topic description and topic examples ,0 At the top of the sequence ,2 At the bottom of the list , therefore , When scanning an array , We can judge the value of the current number ：

• If it is 0, Just move to the front of the sequence ;
• If it is 2, Just move to the back of the sequence .

problem 2： How to move forward and backward ？

At this point, another question is thrown ： Move forward , Where to move ？ Move back , And where to move ？

—— Set two markers flag0 and flag2.

At first, we didn't know how many there would be in the end 0, But the front of the sequence must be 0, therefore flag0 The initial value is the top of the sequence , namely 0; Again , At the beginning, we didn't know how many there were in the end 2, But the last part of the sequence must be 2, therefore flag2 The initial value is the index position of the last element of the array . After initialization , Next, start the scanning process （ That is, update the tag flag0 and flag2 The process of ）：

• If the current element is 0, Index the current element to flag0 The element exchange position of ,flag0++;
• If the current element is 2, Index the current element to flag2 The element exchange position of ,flag2--.

problem 3： If there is no 0 Or not 2 Well ？

If there is no 0, that flag0 Always point to the first position of the array ; Empathy , If there is no 2,flag2 Always index the position of the last element of the array .

problem 4： If the current element is 1, How to deal with ？

Don't deal with ！ Why not deal with it ？ Just because there are two marks flag0 and flag2 The existence of , Because the two tags strictly limit 0 and 2 The boundary of the , Naturally , Between the two boundaries is 1 了 .

03

Code

void swap(vector<int>& nums, int i, int j){
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}
 
void sortColors(vector<int>& nums) {
  // Initialization tag 
  int flag0 = 0;
  int flag2 = nums.size() - 1;
  for (int i = 0; i <= flag2; i++){
    if (nums[i] == 2){
      swap(nums, i, flag2);
      flag2--;
      i--;// Why i--, Because of the exchange to i The value at may be 0
    }
    else if (nums[i] == 0){
      swap(nums, i, flag0);
      flag0++;
    }
  }
}

Copy

04

Execution results